Description

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

There are two types of operations:

• $\texttt{Add x y}$: Add a child to the node numbered $x$ in the tree. The new node’s number is the size of the tree after adding this node, and the edge between it and $x$ has weight $y$.
• $\texttt{Query a b}$: Among all paths starting from $a$ to some node in the subtree of node $b$ (including $b$), find the one with the maximum XOR sum of edge weights, and output that XOR sum.

Input Format

The first line contains an integer $Q$.

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

Output Format

For each $\texttt{Query}$ operation, output one integer per line representing the answer.

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

5
7

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

7
2

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

14
10
13

Hint

【Constraints and Rules】

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

【Hints and Help】

This problem is translated from COCI 2019/2020 CONTEST #4 T4 Klasika.

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

Translated by ChatGPT 5