题目描述

译自 COCI 2019/2020 Contest #4 T4「Klasika」

开始时，有一个编号为 $1$ 的节点，它代表一棵树的根节点。你的任务是支持以下两种形式的 $Q$ 次操作：

• $\texttt{Add x y}$：给树上编号为 $x$ 的节点加一个儿子，新加入的节点和节点 $x$ 之间用一条边权为 $y$ 的边连接，新加入的节点编号等于该节点加入后树上所有的节点数；
• $\texttt{Query a b}$：找到从节点 $a$ 出发，到节点 $b$ 的子树中的节点（节点本身也算作在自己的子树中）的最长路径长度。这里路径的长度定义为在路径上所有边权的异或值。

输入格式

第一行一个正整数 $Q$，与题目描述中意义相同；

接下来 $Q$ 行，每行表示一个操作，格式同题目描述。

输出格式

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

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

数据范围与提示

对于所有数据，$1\le Q\le 2\times 10^5$，保证 $x,a,b$ 是在此时刻存在的节点编号，$y$ 不超过 $2^{30}$。

详细子任务限制及分值如下表：