Problem Description

Initially, you have a node numbered $1$, which represents the root of a tree. Your task is to perform $Q$ operations on the tree.

There are two types of operations:

• Add x y: Add a child to the node numbered $x$. The child's number is the size of the tree after adding this node, and the edge weight between $x$ and this child is $y$.
• Query a b: Find the path with the maximum edge weight XOR sum from node $a$ to any node in the subtree of node $b$ (including $b$), and output this XOR sum.

Input Format

The first line contains an integer $Q$.

The next $Q$ lines each contain a string and two numbers, describing an operation.

Output Format

For each Query operation, output a single integer on a new line representing the answer.

Sample Input and Output

Input Sample #1

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

Output Sample #1

5
7

Input Sample #2

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

Output Sample #2

7
2

Input Sample #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

Output Sample #3

14
10
13

Notes

Data Constraints and Specifications

For $100\%$ of the data, $1\le Q\le 2\times 10^5$, $0\le y\le 2^{30}$, and $x, a, b$ are guaranteed to be less than or equal to the current size of the tree.

Hints and Assistance

Translated from COCI 2019/2020 CONTEST #4 T4 Klasika

In COCI, this problem is worth $110$ points.

见题面 Input 部分

见题面 Output 部分