Có một cây gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$. Tất cả các cạnh đều có trọng số bằng $1$.

Hãy viết chương trình thực hiện các truy vấn sau đây:

• k v_1 r_1 v_2 r_2 ... v_k r_k: Nếu một đỉnh $x$ nằm trong khoảng cách $r_i$ từ $v_i$ (khoảng cách nhỏ hơn hoặc bằng $r_i$), thì ta nói $x$ thỏa mãn điều kiện thứ $i$. Trong tất cả các đỉnh của cây, hãy đếm số lượng đỉnh thỏa mãn ít nhất một trong $k$ điều kiện đã cho trong truy vấn.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$. ($1 \le N \le 100\,000$)

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ là hai đầu mút của một cạnh. ($1 \le u, v \le N$)

Dòng tiếp theo chứa số nguyên $M$. ($1 \le M \le 300\,000$)

$M$ dòng tiếp theo chứa các truy vấn như đã mô tả ở trên. Các truy vấn không được đưa ra trên một dòng như trong phần mô tả, mà được chia thành $k+1$ dòng riêng biệt. Tham khảo ví dụ đầu vào. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

Tổng các giá trị $k$ trong tất cả các truy vấn không vượt quá $300\,000$.

Dữ liệu ra

In ra kết quả của mỗi truy vấn trên một dòng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

10
7