Cho một cây gồm ~n~ đỉnh.

Bạn có một con robot. Bạn có thể đặt nó tại đỉnh ~u~ trên cây và ra lệnh cho nó di chuyển tới đỉnh ~v~ theo đường đi đơn giữa hai đỉnh.

Di chuyển từ đỉnh này sang đỉnh kề tốn ~1~ đơn vị năng lượng. Khi robot hết năng lượng, nó dừng lại.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~(u, v, w)~ — robot xuất phát tại ~u~ và di chuyển về phía ~v~ với ~w~ đơn vị năng lượng ban đầu. Hỏi nó sẽ dừng ở đâu?

Nếu năng lượng đủ để tới ~v~ thì robot dừng tại ~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 hai số nguyên ~u~ và ~v~ — có một cạnh nối ~u~ và ~v~.
• ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ — 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 3
2 4
2 5
3 6
3 7
1 4 1
5 6 2
6 5 3

Đầu ra:

2
1
2

Giải thích: Truy vấn ~(1, 4, 1)~: đường đi là ~1 \to 2 \to 4~, robot đi được ~1~ bước nên dừng tại ~2~. Truy vấn ~(5, 6, 2)~: đường đi là ~5 \to 2 \to 1 \to 3 \to 6~, đi ~2~ bước nên dừng tại ~1~. Truy vấn ~(6, 5, 3)~: đường đi là ~6 \to 3 \to 1 \to 2 \to 5~, đi ~3~ bước nên dừng tại ~2~.

Giới hạn

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

Nếu ~u = v~ thì robot đã ở đích và dừng ngay tại ~u~.