Данное дерево состоит из $N$ вершин. Вершины пронумерованы от $1$ до $N$. Все рёбра имеют вес $1$.

Напишите программу, выполняющую следующие запросы.

• k v_1 r_1 v_2 r_2 ... v_k r_k: Пусть вершина $x$ удовлетворяет условию $i$, если она находится на расстоянии не более $r_i$ от вершины $v_i$ (т.е. расстояние меньше или равно $r_i$). Выведите количество вершин дерева, которые удовлетворяют хотя бы одному из $k$ условий, заданных в запросе.

Входные данные

Первая строка содержит целое число $N$ ($1 \le N \le 100\,000$).

В следующих $N-1$ строках заданы рёбра: каждая строка содержит два целых числа $u, v$ ($1 \le u, v \le N$), номера вершин, соединённых ребром.

Следующая строка содержит целое число $M$ ($1 \le M \le 300\,000$).

Далее идут $M$ запросов, описанных выше. Каждый запрос, в отличие от формулировки в тексте, не помещается в одну строку, а разбивается на $k+1$ строк. Смотрите пример входных данных. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

Сумма значений $k$ по всем запросам не превышает $300\,000$.

Выходные данные

Для каждого запроса выведите результат в отдельной строке.

Примеры

Входные данные 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

Выходные данные 1

10
7