给定一棵 $n$ 个点的树，树上的节点依次编号为 $1$ 到 $n$。这一颗树的根节点为 $1$。

给定一个长度为 $m$ 的正整数序列 $a_1, \cdots, a_m$，满足 $\forall i$，$a_i \in [1,n]$。

$q$ 次询问，每次询问给出 $2k$ 个数 $l_1, r_1, \cdots, l_k, r_k$，满足 $\forall i$，$1 \leq l_i \leq r_i \leq m$。

我们不妨记数组 $a$ 中由这 $k$ 个子区间拼接而成的序列 $a_{l_1}, a_{l_1+1}, \cdots, a_{r_1}, a_{l_2}, a_{l_2+1}, \cdots, a_{r_2},\cdots, a_{l_k}, a_{l_k + 1}, \cdots, a_{r_k}$ 为 $b_1, \cdots, b_s$，你需要求出有几个 $i$ 满足如下条件：

• $1 \leq i \leq s$。
• $\forall 1 \leq j \leq i$，$b_i = b_j$ 或者 $b_i$ 为 $b_j$ 的祖先节点。

输入格式

第一行三个正整数 $n$、$m$、$q$。

接下来 $n-1$ 行，每行两个正整数 $x_i$、$y_i$，表示一条连接 $x_i, y_i$ 的树边。

接下来一行有 $m$ 个数，依次表示 $a_1, \cdots, a_m$。

接下来 $q$ 行，每行第一个正整数表示 $k$，之后 $2k$ 个正整数，依次表示 $l_1, r_1, l_2, r_2, \cdots, l_k, r_k$。

输出格式

$q$ 行，每行一个数表示这一次询问答案。

样例数据

样例输入

5 10 3
1 2
1 3
2 4
2 5
3 5 1 2 5 2 5 1 4 1
1 1 10
2 4 5 6 7
1 4 7

样例输出

4
2
2

子任务

由于本题数据规模可以达到 27MB，请注意自己的 IO 用时。

Subtask 1（$10\%$）：给定的树是一条链。

Subtask 2（$20\%$）：$k = 1$。

Subtask 3（$30\%$）：$n,m,\sum k \leq 100\,000$。

Subtask 4（$40\%$）：无特殊限制。

对于所有测试数据，满足 $n,m,\sum k \leq 700\,000$。