题目描述

小 A 栽下了一棵树。最初时，这棵树只有一个根节点，编号为 $1$。之后，这棵树可能会长高，即在原来的某个节点上用一条边连接一个新孩子节点。小 A 也会来关心这棵树的长势，小 A 会查询从某个节点 $a$ 出发，到达某个节点 $b$ 的子树内的某个节点的所有路径中，边权异或和最大的一条路径的异或和。

输入格式

第一行一个整数 $m$，表示操作。

解下来 $m$ 行，每行一个字符串和两个非负整数，按照如下形式，描述一次操作。

• $\texttt{Add x y}$：给编号为 $x$ 的节点用一条边权为 $y$ 的边连接一个新孩子节点，该新节点的编号为加入该节点后树的大小。
• $\texttt{Query a b}$，查找从 $a$ 出发，到 $b$ 节点子树内某个节点（包括 $b$ ）的路径中边权异或和最大的一条，并输出其异或和。

输出格式

对于每个 $\texttt{Query}$ 操作，一行一个整数表示答案。

样例

样例输入 1

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

样例输出 1

5
7

样例输入 2

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

样例输出 2

7
2

样例输入 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

样例输出 3

14
10
13

样例输入 / 输出 4, 5, 6

见下发文件 tree4/5/6.in/ans。它们分别满足子任务 $2, 3, 4$ 的限制。

数据范围与提示

本题使用捆绑测试。

对于 $100\%$ 的数据，$1\le m\le 2\times 10^5$，$0\le y\le 2^{30}$，保证 $x,a,b$ 小于等于当前树的大小。