Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Mỗi khi có một trận mưa lớn đổ xuống Hà Nội thì ngay sau đó các tuyến đường có hệ thống thoát nước kém sẽ xảy ra tình trạng ngập cục bộ. Việc ngập lụt như vậy còn gây nên những điểm ách tắc giao thông, gây ức chế cho người tham gia giao thông, đặc biệt nếu xảy ra vào khung giờ tan tầm. Đó là điều khiến giáo sư T trăn trở bấy lâu nay. Ông muốn tìm ra giải pháp giúp giải quyết hoàn toàn tình trạng này.

Giáo sư đã chọn ra các tuyến đường thường xuyên bị ngập và phác thảo lại sơ đồ thành phố Hà Nội thành một đồ thị dạng cây, trong đó các đỉnh là các địa điểm trong thành phố, còn các cạnh là các đoạn đường trực tiếp giữa 2 địa điểm. Luôn có đường đi giữa hai đỉnh bất kì trong đồ thị này. Mỗi cạnh có một trọng số thể hiện mức ngập trung bình của đoạn đường. Trong các tuyến đường giữa hai địa điểm, giáo sư chỉ quan tâm đến loại tuyến đường có ít đoạn đường nhất. Để đo đạc, với mỗi tuyến đường giữa hai địa điểm, giáo sư gán giá trị ngập úng bằng mức ngập trung bình lớn nhất giữa các đoạn đường trên tuyến đường đó.

Sau khi đã xây dựng xong công thức, giáo sư cần thực hiện các phép đo đạc. Mỗi phép đo đạc gồm hai tham số l và r, kết quả tương ứng là số lượng tuyến đường giữa hai địa điểm trong thành phố có giá trị ngập úng trong phạm vi [l, r].

Hãy giúp giáo sư T thực hiện công việc tính toán này. Đổi lại nếu bạn hoàn thành, bạn có thể liên hệ qua số điện thoại 0123456789 để trao đổi với giáo sư và có cơ hội được ông nhận làm nghiên cứu sinh.

Input

Dòng đầu tiên gồm 2 số nguyên N và M (1 ≤ N, M ≤ 10⁵) là số lượng địa điểm trong thành phố và số lượng các phép đo đạc. Các địa điểm được đánh số từ 1 đến N.

N – 1 dòng tiếp theo, mỗi dòng gồm 3 số nguyên u, v, w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 10⁹) thể hiện đoạn đường nối địa điểm u và v có mức ngập trung bình là w.

M dòng tiếp theo, mỗi dòng gồm 2 số nguyên l và r (1 ≤ l ≤ r ≤ 10⁹) là tham số của các phép đo đạc.

Output

Gồm M dòng là kết quả tương ứng của các phép đo đạc.

Example

Input:
4 3
1 2 5
1 3 1
4 3 7
1 1
3 5
5 7

Output:
1
2
5