Given a tree with $n$ nodes, labeled from $1$ to $n$. The root of the tree is $1$.

Given a sequence of $m$ positive integers $a_1, \cdots, a_m$, where $\forall i$, $a_i \in [1, n]$.

There are $q$ queries. Each query provides $2k$ integers $l_1, r_1, \cdots, l_k, r_k$, where $\forall i$, $1 \leq l_i \leq r_i \leq m$.

Let the sequence formed by concatenating the $k$ sub-intervals of $a$ be $b_1, \cdots, b_s$, where the sequence is $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}$. You need to find the number of indices $i$ that satisfy the following conditions:

• $1 \leq i \leq s$.
• $\forall 1 \leq j \leq i$, $b_i = b_j$ or $b_i$ is an ancestor of $b_j$.

Input

The first line contains three positive integers $n$, $m$, and $q$.

The next $n-1$ lines each contain two positive integers $x_i$ and $y_i$, representing an edge connecting $x_i$ and $y_i$ in the tree.

The next line contains $m$ integers, representing $a_1, \cdots, a_m$.

The next $q$ lines each start with a positive integer $k$, followed by $2k$ positive integers representing $l_1, r_1, l_2, r_2, \cdots, l_k, r_k$.

Output

For each query, output one integer on a new line representing the answer.

Examples

Input 1

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

Output 1

4
2
2

Subtasks

Since the input data size can reach 27MB, please be mindful of your I/O performance.

Subtask 1 ($10\%$): The given tree is a chain.

Subtask 2 ($20\%$): $k = 1$.

Subtask 3 ($30\%$): $n, m, \sum k \leq 100\,000$.

Subtask 4 ($40\%$): No additional constraints.

For all test cases, $n, m, \sum k \leq 700\,000$.