Ban đầu có một nút được ký hiệu là ~1~ và nó đại diện cho gốc của một cây. Nhiệm vụ của bạn là hỗ trợ ~Q~ truy vấn dưới dạng:

• ~Add~ ~x~ ~y~ – Thêm một nút mới vào cây như là con của nút ~x~. Nút mới được thêm vào và nút ~x~ được kết nối với một cạnh có trọng số ~y~. Nút mới được ký hiệu bằng một số bằng số lượng nút mà cây có sau khi thêm nút mới.
• ~Query~ ~a~ ~b~ – Tìm đường đi dài nhất trong cây bắt đầu từ nút ~a~ và kết thúc tại một nút nào đó từ cây con của nút ~b~ (chính bản thân nó cũng được coi là trong cây con của mình). Độ dài của đường đi được định nghĩa là phép exclusive or (xor) của trọng số của tất cả các cạnh mà đường đi bao gồm.

Input

• Dòng đầu tiên chứa một số nguyên ~Q~ ~(1 \leq Q \leq 200000)~ từ mô tả bài toán.
• Dòng thứ ~i~ trong số ~Q~ dòng tiếp theo chứa truy vấn thứ ~i~ có định dạng tương ứng với một trong các truy vấn từ mô tả bài toán. Các giá trị ~x, a~ và ~b~ sẽ tham chiếu đến một nút tồn tại tại thời điểm đó và giá trị ~y~ sẽ không lớn hơn ~2^{30}~.

Output

Bạn nên xuất ra câu trả lời cho mỗi truy vấn loại Query. Mỗi câu trả lời nên được in ra trong một dòng riêng biệt theo thứ tự các truy vấn tương ứng xuất hiện trong đầu vào.

Chú ý

• Nhóm 1 (11 điểm): ~Q \leq 200~.
• Nhóm 2 (22 điểm): ~Q \leq 2000~.
• Nhóm 3 (33 điểm): Trong tất cả các truy vấn loại ~Query~ đều có ~b = 1~.
• Nhóm 4 (44 điểm): Không có ràng buộc bổ sung nào.

Sample Input 1

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1

Sample Ouput 1

5
7

Sample Input 2

6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

Sample Ouput 2

7
2

Sample Input 3

10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3

Sample Ouput 3

14
10
13