Cho ~n~ đồi chè đánh số từ ~1~ đến ~n~ và ~n-1~ đường đi trực tiếp sao cho từ một đồi chè luôn có đường đi tới một đồi chè khác. Chi phí đi từ đồi chè ~i~ đến đồi chè ~j~ là một số nguyên dương ~c_{ij}~.

Một đường đi đơn từ đồi chè ~u~ đến đồi chè ~v~ là dãy ~u=x_1,x_2,\dots,x_k=v~ trong đó ~(x_i,x_{i+1})~, ~i=1,\dots,k-1~, là đường đi trực tiếp và các đồi chè trên đường đi đôi một khác nhau. Chi phí của đường đi trên là giá trị nhỏ nhất của các đường nối trực tiếp giữa hai đồi chè kề nhau nằm trên đường đi đó.

Yêu cầu: Cho ~Q~ truy vấn, mỗi truy vấn được mô tả bởi hai số nguyên ~k, v~ với ý nghĩa: Đếm xem có bao nhiêu đồi chè ~u~ mà đường đi đơn từ đồi chè ~u~ đến đồi chè ~v~ có chi phí không nhỏ hơn ~k~.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n, Q~ ~(1 \le n, Q \le 10^5)~;

• ~n-1~ dòng sau mô tả các đường nối trực tiếp giữa các đồi chè. Dòng thứ ~i~ chứa ba số nguyên dương ~p_i, q_i, c_i~ thể hiện có đường đi từ đồi chè ~p_i~ đến đồi chè ~q_i~ với chi phí ~c_i~ ~(1 \le p_i, q_i \le n, 1 \le c_i \le 10^9)~;

• ~Q~ dòng tiếp theo, mỗi dòng ghi một truy vấn gồm hai số nguyên ~k, v~ ~(1 \le k \le 10^9, 1 \le v \le n)~ thể hiện yêu cầu đếm xem có bao nhiêu đồi chè mà chi phí đường đi đơn từ nó đến đồi chè ~v~ không nhỏ hơn ~k~.

Output

Gồm ~Q~ dòng, mỗi dòng ghi một số nguyên là kết quả của truy vấn tương ứng theo thứ tự xuất hiện trong dữ liệu vào.

Scoring

Sample Input 1

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

Sample Output 1

3
0
2