Hay un árbol con $N$ vértices. Los vértices están numerados del $1$ al $N$. Todos los pesos de las aristas son $1$.

Escriba un programa que procese las siguientes consultas.

• k v_1 r_1 v_2 r_2 ... v_k r_k: Sea $x$ un vértice. Si $x$ está a una distancia menor o igual que $r_i$ de $v_i$, entonces se dice que $x$ satisface la condición $i$. Entre todos los vértices del árbol, imprima la cantidad de vértices que satisfacen al menos una de las $k$ condiciones dadas en la consulta.

Entrada

La primera línea contiene un entero $N$. ($1 \le N \le 100{,}000$)

Las siguientes $N-1$ líneas contienen dos enteros $u, v$ que representan los vértices conectados por cada arista. ($1 \le u, v \le N$)

La siguiente línea contiene un entero $M$. ($1 \le M \le 300{,}000$)

Luego vienen $M$ consultas como se describió anteriormente. Cada consulta no se proporciona en una sola línea, sino que se divide en $k + 1$ líneas. Consulte la entrada de ejemplo. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

La suma de todos los $k$ en las consultas no supera $300000$.

Salida

Imprima el resultado de cada consulta en una línea separada.

Ejemplos

Entrada 1

10
1 3
6 4
9 8
1 8
3 4
2 8
10 3
4 5
8 7
2
3
8 1
3 1
3 2
2
7 3
6 0

Salida 1

10
7