Trong thời gian rảnh rỗi, Nông dân John đã tạo ra một dịch vụ chia sẻ video mới, anh ta đặt tên là JohnTube. Trên JohnTube, những con bò của Nông dân John có thể ghi lại, chia sẻ và khám phá nhiều video thú vị. Những con bò của anh ấy đã đăng ~N~ video, được đánh số từ 1 đến ~N~.

FJ muốn tạo một danh sách "video được đề xuất" cho mỗi video JohnTube. FJ đưa ra một số liệu về "mức độ liên quan", xác định hai video có liên quan với nhau như thế nào. Anh ta chọn ~N - 1~ cặp video và tự tính toán mức độ liên quan giữa 2 video này. FJ hình dung các video của mình như một mạng, trong đó mỗi video là một nút và ~N-1~ cặp video đã xác định mức độ liên quan là các kết nối giữa những video. Thông qua ~N-1~ cặp video này, FJ có thể truy cập bất kỳ video nào khác dọc theo đường kết nối giữa các video theo đúng một cách duy nhất.

FJ quy định rằng mức độ liên quan của bất kỳ cặp video nào phải được xác định là mức độ liên quan tối thiểu của một kết nối nào đó trên đường kết nối giữa 2 video này.

Nông dân John muốn chọn một giá trị ~K~ mức độ liên quan để bên cạnh bất kỳ video JohnTube cụ thể nào, tất cả các video khác có mức độ liên quan ít nhất ~K~ với video đó sẽ được đề xuất. Nông dân John muốn bạn giúp trả lời một số câu hỏi về các video được đề xuất cho các giá trị nhất định của ~K~.

Yêu cầu: Với mỗi câu hỏi, hãy cho biết có bao nhiêu video sẽ được đề xuất cho người xem video ~v_j~ nếu ~K = k_j~.

Input

• Dòng 1 ghi 2 số nguyên dương ~n~ và ~Q~ (~1 \le n, Q \le 10^5~);
• ~n-1~ dòng tiếp theo, mỗi dòng mô tả một cặp video gồm ba số nguyên ~p_i, q_i~ và ~r_i~ cho biết rằng video ~p_i~ và ~q_i~ được kết nối với nhau với mức độ liên quan là ~r_i~ (~1 \le p_i, q_i \le n~, ~1 \le r_i, k_j \le 10^9~);
• ~Q~ dòng tiếp theo, mỗi dòng mô tả câu hỏi gồm hai số nguyên ~k_j~ và ~v_j~ (~1 \le v_j \le n~; ~1 \le j \le Q~).

Output

• Ghi ra ~Q~ dòng, dòng thứ i ghi câu trả lời cho câu hỏi thứ i.

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