Cho một đồ thị cây có N đỉnh N-1 cạnh, có gốc là đỉnh 1. và M truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:

• 1 root: Chọn root làm gốc của cây
• 2 u v: Yêu cầu tìm cha chung gần nhất của hai đỉnh u và v.

Hãy lập trình và đưa ra câu trả lời ứng với các truy vấn loại 2.

Input

Gồm nhiều bộ test:

• Dòng 1: Số nguyên N, số đỉnh của cây (1≤N≤10^5).
• N-1 dòng tiếp theo: Mỗi dòng gồm hai số nguyên u và v là hai đỉnh của đồ thị.
• Dòng tiếp theo: Số nguyên M, số truy vấn (1≤M≤10^5).
• M dòng tiếp theo, mỗi dòng thuộc một trong hai loại truy vấn đã cho: “! root” ứng với truy vấn loại 1 và “? u v” ứng với truy vấn loại 2.
• Kết thúc bộ test là số 0.

Output

Đưa ra các câu trả lời ứng với các bộ, mỗi câu trả lời in ra trên một dòng.

Example

Input
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
0

Output
2
1
3
6