Dany jest ciąg wierzchołków $N$ tworzących drzewo. Wierzchołki są ponumerowane od $1$ do $N$. Wagi wszystkich krawędzi są równe $1$.

Napisz program realizujący następujące zapytania:

• k v_1 r_1 v_2 r_2 ... v_k r_k: Mówimy, że wierzchołek $x$ spełnia warunek $i$, jeśli znajduje się on w odległości nie większej niż $r_i$ od $v_i$ (tj. odległość jest mniejsza lub równa $r_i$). Spośród wszystkich wierzchołków drzewa wypisz liczbę tych, które spełniają co najmniej jeden z $k$ warunków podanych w zapytaniu.

Wejście

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

Następne $N-1$ wierszy zawiera dwie liczby całkowite $u, v$ – numery wierzchołków połączonych krawędzią. ($1 \le u, v \le N$)

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

Następnie podanych jest $M$ zapytań w formacie opisanym powyżej. Każde zapytanie, w przeciwieństwie do opisu w treści, nie jest podane w jednym wierszu, lecz jest podzielone na $k+1$ wierszy. Sprawdź przykładowe wejście. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

Suma wartości $k$ we wszystkich zapytaniach nie przekracza $300\,000$.

Wyjście

Wypisz wyniki zapytań, każdy w osobnym wierszu.

Przykład

Wejście

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

10
7