Dane jest drzewo składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$. Wagi krawędzi są równe $1$.

Napisz program wykonujący poniższe zapytania:

• k v_1 r_1 v_2 r_2 ... v_k r_k: Niech wierzchołek $x$ spełnia warunek $i$, jeśli znajduje się w odległości co najwyżej $r_i$ od $v_i$ (tj. odległość jest mniejsza lub równa $r_i$). Dla wszystkich wierzchołków w drzewie, wypisz liczbę tych, które spełniają co najmniej $k-1$ spośród $k$ warunków podanych w zapytaniu.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $N$ ($1 \le N \le 100\,000$).

Kolejne $N-1$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le N$) oznaczające krawędź łączącą wierzchołki $u$ i $v$.

Następny wiersz zawiera liczbę całkowitą $M$ ($1 \le M \le 300\,000$).

Kolejne $M$ zapytań jest podanych w postaci opisanej powyżej. Każde zapytanie, w odróżnieniu od opisu, nie jest podane w jednym wierszu, ale jest rozdzielone na $k+1$ wierszy. Zapoznaj się z przykładowym wejściem. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

Suma wartości $k$ ze wszystkich zapytań nie przekracza $300\,000$.

Wyjście

Dla każdego zapytania wypisz w osobnym wierszu wynik.

Przykład

Wejście 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

Wyjście 1

5
7