Cho một cây gồm ~n~ đỉnh, gọi ~d(u, v)~ là số cạnh trên đường đi đơn từ ~u~ đến ~v~. Cho ~q~ truy vấn có 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.

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 ~a~, ~b~, ~c~ — một truy vấn.

Kết quả

Với mỗi truy vấn, in ra đỉnh thỏa mãn điều kiện, mỗi đáp án trên một dòng.

Ví dụ

Đầu vào:

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

Đầu ra:

4
1
4
5
2
5
1

Giải thích: Với truy vấn ~(4, 4, 2)~, chọn ~x = 4~ cho tổng ~0 + 0 + 1 = 1~, nhỏ nhất có thể. Với ~(1, 5, 8)~, đỉnh ~1~ nằm trên cả ba đường đi đôi một nên cho tổng nhỏ nhất.

Giới hạn

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

Đỉnh làm cho tổng nhỏ nhất luôn tồn tại và là duy nhất — đó chính là đỉnh nằm trên cả ba đường đi ~a \to b~, ~b \to c~ và ~a \to c~. Các đỉnh ~a~, ~b~, ~c~ không nhất thiết phân biệt.