Cho một cây ~N~ đỉnh.

Cho ~Q~ truy vấn, truy vấn thứ ~i~ được biểu diễn bởi ~K_i~ đỉnh ~(v_j, radius_j)~, nghĩa là đỉnh ~v_j~ sẽ đánh dấu tất cả các đỉnh có khoảng cách tới nó không vượt quá ~radius_j~. Với mỗi truy vấn hãy tính số lượng đỉnh trên cây được đánh dấu.

Input

Dòng đầu tiên gồm số ~N (1 \leq N \leq 5 \times 10^{4})~.

~N - 1~ dòng tiếp theo là các cạnh của cây.

Dòng tiếp theo gồm số ~Q (1 \leq Q \leq 5 \times 10^{5} + N)~.

~Q~ dòng sau đó là các truy vấn, bắt đầu bằng số ~K_i~ và sau đó là các cặp ~(v_j, radius_j)~.

Output

In ra ~Q~ dòng là đáp án cho ~Q~ truy vấn

Example

4
2 1
3 1
4 3
5
1 1 1
1 4 1
2 2 1 3 1
1 2 1
2 1 1 1 1

3
2
4
2
3