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

Écrivez un programme qui exécute les requêtes suivantes.

• k v_1 r_1 v_2 r_2 ... v_k r_k : Soit un sommet $x$. On dit que $x$ satisfait la condition $i$ s'il se trouve à une distance au plus $r_i$ de $v_i$ (c'est-à-dire si la distance est inférieure ou égale à $r_i$). Parmi tous les sommets de l'arbre, affichez le nombre de sommets qui satisfont au moins $k-1$ 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$ indiquant les extrémités d'une arête. ($1 \le u, v \le N$)

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

Les $M$ lignes suivantes contiennent les requêtes telles que décrites ci-dessus. Contrairement à la description, chaque requête n'est pas 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

Affichez le résultat de chaque requête sur une ligne distincte.

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

5
7