You are given an unrooted tree with $n$ nodes, labeled starting from $1$, and an initially empty multiset $S$. There are $m$ operations to add elements to $S$. In the $i$-th operation, you are given $k_i$ distinct edges of the original tree. You must remove these $k_i$ edges, resulting in $k_i + 1$ connected components. Let the sets of node labels forming these components be $T_{i,1}, T_{i,2}, \dots, T_{i,k_i+1}$. You must add these sets to $S$. Note that each operation is independent.

After all $m$ addition operations, there are $q$ queries. In the $i$-th query, you are given a node $u_i$ and a radius $r_i$ on the tree. Let $C_i$ be the set of labels of all nodes whose distance (number of edges) from $u_i$ in the original tree is at most $r_i$. You need to find how many elements in $S$ are subsets of $C_i$.

Input

The first line contains four positive integers $subid, n, m, q$, where $subid$ indicates the special properties of Subtask #id, and the others are as described above.

The next $n-1$ lines each contain two positive integers $a_i, b_i$, representing the two endpoints of the edge with label $i$ in the tree.

The next $m$ lines each start with a positive integer $k_i$, followed by $k_i$ positive integers representing the labels of the edges removed in this operation. It is guaranteed that these edges are valid and distinct.

The next $q$ lines each contain two integers $u_i, r_i$, representing the given node label and radius.

Output

Output $q$ lines, where the $i$-th line contains the answer to the $i$-th query.

Examples

Input 1

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

Output 1

3
2
1

Input 2

1 15 3 5
12 7
5 13
1 5
1 6
15 1
4 11
1 3
4 8
1 2
1 7
3 4
13 14
10 6
9 4
2 1 10
2 6 12
2 3 12
4 2
1 0
15 3
8 5
6 5

Output 2

1
0
3
6
9

Constraints

For all test cases, $1 \le n \le 10^5$, $1 \le m+\sum k, q \le 3 \times 10^5$, and $\forall i, 0 \le r_i \le n$.