Cho một cây có trọng số gồm ~n~ đỉnh, gốc tại đỉnh ~1~.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v)~ — hãy tìm trọng số của cạnh nặng nhất trên đường đi đơn giữa ~u~ và ~v~.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n - 1~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — có một cạnh trọng số ~w~ nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ — một truy vấn.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

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

Đầu ra:

3
2
1

Giải thích: Đường đi ~4 \to 2 \to 5~ có các cạnh trọng số ~3~ và ~2~, nặng nhất là ~3~. Đường đi ~2 \to 1 \to 3 \to 6~ có các cạnh ~1~, ~2~, ~1~, nặng nhất là ~2~. Đường đi ~2 \to 1~ chỉ có một cạnh trọng số ~1~.

Giới hạn

• ~1 \le n, q \le 10^5~
• ~1 \le u, v \le n~
• ~1 \le w \le 10^9~

Nếu ~u = v~ thì đường đi không có cạnh nào, khi đó đáp án là ~0~.