Tree Query

Problem

Cho một cây có ~n~ đỉnh (đánh số ~1..n~), mỗi cạnh ~(a,b)~ có trọng số dương ~w~. Khoảng cách giữa hai đỉnh là tổng trọng số trên đường đi duy nhất nối chúng.

Bạn được yêu cầu trả lời ~q~ truy vấn. Mỗi truy vấn cho biết một đỉnh ~v~ và một ngưỡng ~L~, hãy đếm số đỉnh ~u~ (kể cả ~v~) sao cho

~~ \text{dist}(v,u) \le L. ~~

Input

n q
n-1 dòng sau: a b w     (1 ≤ a,b ≤ n, 1 ≤ w ≤ 10^9)
q dòng sau:  v L        (1 ≤ v ≤ n, 1 ≤ L ≤ 10^14)

Output

• Với mỗi truy vấn, in ra một số nguyên trên một dòng — số đỉnh thỏa mãn.

Constraints

• ~1 \le n, q \le 10^5~
• Cây: tổng cạnh = ~n-1~
• Trọng số cạnh dương, ~L~ có thể rất lớn (đến ~10^{14}~)
• Thời gian: \~2s, bộ nhớ: \~256MB (mục tiêu Codeforces/DMOJ)

Ví dụ

Input

5 5
1 2 3
2 3 2
2 4 4
4 5 1
1 0
1 3
4 3
5 2
3 10

Output

1
2
3
2
5