Cho một cây có \(n\) đỉnh. Ta có \(d(u,v)\) là số lượng cạnh trên đường đi đơn từ \(u\) tới \(v\). Cho \(q\) truy vấn dạng \((a,b,c)\), hãy tìm một đỉnh \(x\) sao cho \(d(a,x)+d(b,x)+d(c,x)\) là nhỏ nhất có thể.

Dữ liệu vào

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

Dữ liệu ra

• Với mỗi truy vấn, in ra đỉnh thỏa mãn.

Ràng buộc

• \(1 \le n,q \le 10^5\)
• \(1 \le a,b,c \le n\)

Input 1

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

Output 1

4
1
4
5
2
5
1