Il y a un arbre constitué de $N$ sommets. Les sommets sont numérotés de $1$ à $N$. Toutes les arêtes ont un poids de $1$.

Écrivez un programme qui effectue la requête suivante.

• k v_1 r_1 v_2 r_2 ... v_k r_k : On dit qu'un sommet $x$ satisfait la $i$-ème condition si $x$ se trouve à une distance au plus $r_i$ de $v_i$ (c'est-à-dire distance $\le r_i$). Parmi tous les sommets de l'arbre, affichez le nombre de sommets qui satisfont au moins une des $k$ conditions données dans la requête.

Entrée

La première ligne contient un entier $N$ ($1 \le N \le 100\,000$).

Les $N-1$ lignes suivantes contiennent chacune deux entiers $u, v$ ($1 \le u, v \le N$) représentant les extrémités d'une arête.

La ligne suivante contient un entier $M$ ($1 \le M \le 300\,000$).

Les $M$ lignes suivantes contiennent les requêtes décrites ci-dessus. Contrairement à l'énoncé, chaque requête n'est pas donnée sur une seule ligne, mais est répartie sur $k+1$ lignes. Référez-vous à l'exemple d'entrée. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

La somme des $k$ sur toutes les requêtes ne dépasse pas $300\,000$.

Sortie

Pour chaque requête, affichez son résultat sur une ligne séparée.

Exemples

Entrée 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

Sortie 1

10
7