Cho một đồ thị cây có ~N~ đỉnh, ~N-1~ cạnh và ~Q~ truy vấn. Mỗi truy vấn được cho bởi bộ 3 số ~(u, v, r)~ yêu cầu hãy tìm ~LCA(u,v)~ khi chọn đỉnh ~r~ làm gốc.

Input

Vào từ file ROOTLESS.INP:

• Dòng đầu ghi số ~N, Q\ (1 \le N, Q \le 10^5)~ là số đỉnh của cây, số truy vấn.
• ~N-1~ dòng tiếp ghi cặp số ~(u, v)\ (1 \le u, v \le N)~ mô tả cạnh của cây.
• ~Q~ dòng tiếp theo mô tả truy vấn, mỗi dòng chứa bộ số ~(u,v,r)\ (1 \le u,v,r \le N)~.

Output

Ghi ra tệp ROOTLESS.OUT:

• Gồm ~Q~ dòng, dòng ~i~ gồm một số nguyên là câu trả lời của truy vấn thứ ~i~.

Sample Input 1

4
1 2
2 3
1 4
2
1 4 2
2 4 2

Sample Output 1

1
2

Giải thích