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,radiu{s}_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á $radiu{s}_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\le N\le 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\le Q\le 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,radiu{s}_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