Tree XOR Path Query

You are given a rooted tree with an initial single node with id \(1\), which acts as the root. The tree will be modified by \(Q\) operations. There are two types of operations:

• Add x y: Attach a new node as a child of node \(x\). The new node's id is equal to the current size of the tree after insertion, and the weight on the edge from \(x\) to the new node is \(y\).
• Query a b: Consider the unique simple path from node \(a\) to some node \(v\) in the subtree of node \(b\) (including \(b\) itself). Let \(f(u)\) denote the XOR sum of the edge weights on the path from the root to node \(u\). The answer to the query is the maximum value of \(f(a) \oplus f(v)\) over all nodes \(v\) in the subtree of \(b\).

Note: For any two nodes \(u\) and \(v\), the XOR sum on the path from \(u\) to \(v\) can be computed as \(f(u) \oplus f(v)\) due to the cancellation of the common prefix in the XOR sums.

Input Format: The input begins with an integer \(Q\), which indicates the number of operations. Each of the following \(Q\) lines represents an operation in one of the two formats described above.

Output Format: For each Query operation, print the maximum XOR value on a separate line.

inputFormat

The first line contains an integer \(Q\) (the number of operations). The next \(Q\) lines each contain an operation in one of the following forms:

• Add x y: Add a new node as a child of node \(x\) with edge weight \(y\). The new node's id is the new size of the tree.
• Query a b: Query the maximum value of \(f(a) \oplus f(v)\) among all nodes \(v\) in the subtree of node \(b\) (including \(b\)). Here, \(f(u)\) is the XOR sum from the root to \(u\).

outputFormat

For each Query operation, output a single line containing the maximum XOR value.

sample

6
Add 1 3
Add 1 5
Add 2 2
Query 1 1
Query 2 2
Query 3 2

5
2
6