Vương quốc Lakasi

Vương quốc Lakasi là một vương quốc mới thành lập, nhà vua muốn mở rộng phạm vi lãnh thổ nên quyết định đi khai phá các vùng đất mới. Nhà vua quyết định mỗi một vùng đất sau khi khai thác thì xây dựng một thành phố ở đó cùng với đó là các con đường nối giữa các thành phố với nhau sao cho khi hoàn thành công việc mở rộng lãnh thổ thì tất cả các thành phố và các con đường tạo thành một đồ thị dạng cây. Hiện ban đầu nhà vua đang ở thủ đô và xem đó như là đỉnh \(1\). Các thành phố còn lại xem như là các đỉnh con trong cây có gốc là đỉnh \(1\). Trong quá trình xây dựng, có \(Q\) sự kiện diễn ra gồm 2 loại:

• Add x y -- thêm một đỉnh mới là một đỉnh con có đường đi độ dài \(y\) nối với đỉnh \(x\). Đỉnh mới được thêm sẽ có chỉ số bằng số lượng đỉnh trong đồ thị hiện tại.

• Query a b -- Nhà vua muốn biết độ dài đường đi dài nhất bắt đầu từ đỉnh \(a\) đến một đỉnh bất kỳ nằm trong cây con gốc \(b\) là bao nhiêu. Độ dài của một đường đi được tính bằng tổng xor (exclusive or) của tất cả các con đường thuộc đường đi đó.

Đối với sự kiện loại 2, hãy trả lời câu hỏi của nhà vua.

Input

• Dòng đầu tiên chứa một số nguyên dương \(Q\) \((Q\leq 200000)\).

• \(Q\) dòng tiếp theo, mỗi dòng có dạng 1 trong 2 sự kiện trên. Các giá trị \(x,a,b\) không vượt quá số lượng đỉnh hiện tại, giá trị \(y\) không quá \(2^{30}\).

Output

• Với sự kiện loại 2, hãy in ra đường đi dài nhất bắt đầu từ đỉnh \(a\) đến một đỉnh bất kỳ nằm trong cây con gốc \(b\).

Example

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

5
7

Scoring

• Subtask 1 (\(10\%\) số điểm): \(Q\leq 200\).

• Subtask 2 (\(25\%\) số điểm): \(Q\leq 2000\).

• Subtask 3 (\(25\%\) số điểm): Tất cả sự kiện loại 2 đều có \(b=1\).

• Subtask 4 (\(40\%\) số điểm): Không có giới hạn gì thêm.