Cho một đồ thị vô hướng gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Ban đầu đồ thị không có cạnh.

Ta khởi gán biến \(res = 0\). Sau đó, ta sẽ thực hiện \(n - 1\) yêu cầu, mỗi yêu cầu thuộc một trong hai dạng sau:

• 1 x y: Đặt \(u = x \oplus res, v = y \oplus res\). Thêm một cạnh nối hai đỉnh \(u\) và \(v\). Dữ liệu vào đảm bảo \(1 \le u, v \le n\) và trước đó trên đồ thị không có đường đi giữa \(u\) và \(v\).
• 2 x y: Thêm một cạnh nối hai đỉnh \(x\) và \(y\). Dữ liệu vào đảm bảo \(1 \le x, y \le n\) và trước đó trên đồ thị không có đường đi giữa \(x\) và \(y\).

Dễ thấy, sau mỗi thao tác, đồ thị luôn gồm một hoặc nhiều thành phần liên thông, và mọi thành phần liên thông đều là cây. Ta gọi \(sum\_dia\) là tổng độ dài đường kính của các cây (đường kính của cây là số cạnh của đường đi có nhiều cạnh nhất trên cây). Ta thực hiện phép gán \(res \leftarrow res \oplus sum\_dia\).

Hãy in ra giá trị của biến \(res\) sau mỗi thao tác.

Nhắc lại, phép toán \(\oplus\) (xor) đối với bit được định nghĩa như sau:

• \(0 \oplus 0 = 0\)
• \(1 \oplus 0 = 1\)
• \(0 \oplus 1 = 1\)
• \(1 \oplus 1 = 0\)

Phép toán \(\oplus\) đối với các số có nhiều hơn một bit được thực hiện theo từng bit. Ví dụ:

• \(2 \oplus 3 = 1\) (\(10_2 \oplus 11_2 = 01_2\))
• \(2 \oplus 5 = 7\) (\(010_2 \oplus 101_2 = 111_2\))
• \(5 \oplus 5 = 0\) (\(101_2 \oplus 101_2 = 000_2\))

Input

• Dòng đầu chứa số nguyên \(n\) (\(2 \le n \le 2 \cdot 10^5\)).
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa \(3\) số nguyên \(t, x, y\) (\(1 \le t \le 2; 0 \le x, y \le 2 \cdot n\)) mô tả một thao tác.

Output

• In ra \(n - 1\) dòng, mỗi dòng là giá trị của biến \(res\) sau mỗi yêu cầu.

Example

8
1 4 8
1 3 2
1 2 6
2 5 3
2 6 3
2 7 1
1 13 6

1
3
0
4
0
5
0

7
2 4 3
2 1 5
2 2 6
1 3 1
1 3 2
1 4 7

1
3
0
4
1
4

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n \le 10^3\).
• Subtask \(2\) (\(33\%\) số điểm): Không có yêu cầu loại \(1\).
• Subtask \(3\) (\(37\%\) số điểm): Không có ràng buộc gì thêm.