题目描述

开始时，你有一个编号为 $1$ 的节点，它代表着一棵树的根。你的任务是对树进行 $Q$ 次操作。

操作分为两类：

• $\texttt{Add x y}$，给树上编号为 $x$ 的节点加入一个儿子，该儿子的编号为加入该节点后树的大小，它与 $x$ 的边的边权为 $y$。
• $\texttt{Query a b}$，查找从 $a$ 出发，到 $b$ 节点子树内某个节点（包括 $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

提示

【数据规模与约定】

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

【提示与帮助】

题目译自 COCI 2019/2020 CONTEST #4 T4 Klasika

在 COCI 中，本题分值为 $110$ 分。