Cho một cây \(n\) đỉnh.

Bạn có một con robot. Bạn có thể đặt nó ở đỉnh \(u\) và lệnh cho nó di chuyển đến đỉnh \(v\) theo đường đi đơn giữa \(2\) đỉnh.

Việc di chuyển từ đỉnh này sang đỉnh khác tốn \(1\) năng lượng. Nếu robot hết năng lượng, nó sẽ dừng lại.

Cho \(q\) truy vấn có dạng \((u,v,w)\), đặt robot ở vị trí \(u\), di chuyển đến \(v\) với \(w\) năng lượng. Robot sẽ dừng ở đâu?

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,q\).
• \(n-1\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\) thể hiện có cạnh nối \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên \(u,v,w\), một truy vấn.

Dữ liệu ra

• In ra \(n\) số nguyên, đáp án của \(q\) truy vấn.

Điều kiện

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

Input 1

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

Output 1

2
1
2