Trong một cây có gốc, tổ tiên chung nhỏ nhất của hai nút ~ u,v ~ là nút thấp nhất làm tổ tiên chung của hai nút ~ u,v ~; ký hiệu là ~ lca(u,v) ~. Bạn được cho một cây gồm ~ n ~ nút. Hãy trả lời ~ q ~ truy vấn dạng ~ r,u,v ~; nghĩa là hãy tìm ~ LCA(u,v) ~ với gốc cây là nút ~ r ~

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~ n ~ ~ (1 ≤ n ≤ 10^5) ~ cho biết số nút trên cây.
• ~ n - 1 ~ dòng tiếp theo mỗi dòng ghi hai số ~ x, y ~ ~ (1 ≤ x,y ≤ n) ~ cho biết một cạnh trên cây.
• Dòng tiếp theo ghi số nguyên ~ q ~ ~ (1≤q≤10^5) ~ cho biết số lượng truy vấn.
• ~ q ~ dòng tiếp theo, mỗi dòng ghi 3 số ~ r,u,v ~ cho biết một truy vấn.

Kết quả

• Gồm ~ q ~ dòng, mỗi dòng trả lời cho một truy vấn tưng ứng trong Input.

Ràng buộc

Ví dụ:

Input 1

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

```

Output 1

1
2