Cho một cây có ~N~ đỉnh được đánh số từ ~1~ đến ~N~.

Cạnh nối ~2~ đỉnh ~U[i]~ và ~V[i]~ có trọng số ~W[i]~.

Cần trả lời ~Q~ truy vấn có dạng ~(X, Y):~ Tính trung vị của dãy số tạo bởi trọng số các cạnh từ đỉnh ~X~ đến đỉnh ~Y~?

Trung vị của một dãy số độ dài ~L~ được tính như sau:

• Nếu ~L~ lẻ, trung vị bằng số nhỏ thứ ~(L+1)/2~.

• Nếu ~L~ chẵn, trung vị bằng trung bình cộng của số nhỏ thứ ~L/2~ và ~L/2+1~.

Ví dụ trung vị của dãy ~[5, 7, 3, 5, 1]~ là ~5~.

Dãy ~[5, 7, 3, 5, 1, 4]~ có trung vị là ~(4+5)/2 = 4.5~.

Input

• Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~Q~ ~(1 \le N \le 5 \times 10^4; 1 \le Q \le 10^5)~.

• Trong ~N-1~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên dương ~U, V, W~ biểu diễn một cạnh nối ~2~ đỉnh ~U~ và ~V~ có trọng số ~W~ ~(1 \le U, V \le N; U ≠ V; 1 \le W \le 10^5)~.

• Trong ~Q~ dòng cuối cùng, mỗi dòng chứa ~2~ số nguyên dương ~X~ và ~Y~ biểu diễn một truy vấn ~(1 \le X, Y \le N; X ≠ Y)~.

Output

Gồm ~Q~ dòng, mỗi dòng ghi kết quả của truy vấn tương ứng.

Kết quả được làm tròn đến ~1~ chữ số phần thập phân.

Sample Input 1

6 3
1 2 9
2 4 7
2 5 5
3 5 1
3 6 4
1 3
2 6
4 6

Sample Output 1

5.0
4.0
4.5