单点时限: 4.0 sec
内存限制: 1024 MB
你需要维护一棵动态树，初始状态下仅有一个节点，编号为 $1$，并支持以下操作：
Add x y：插入一个节点，其编号为当前存在的节点数量（包括当前新加入的节点），指定其父节点为 $x$，并添加一条无向边连接新节点和它的父节点，边权为 $y$。
Query x y：查询起点为 $x$ 号节点，终点在 $y$ 的子树中（包括 $y$ 号节点）的最大简单路径异或和（要求路径不经过重复的节点，且起点与终点不同）。若一条路径上所有边的边权分别为 $a_1,a_2,\dots,a_k$，则路径异或和为 $a_1 \oplus a_2 \oplus \dots \oplus a_k$。其中 $\oplus$ 为按位异或操作，它在 C++、Java 等语言中以 ^ 来表示。
第一行，一个正整数 $Q$（$1 \le Q \le 2\cdot 10^5$）。
接下来 $Q$ 行，每行依次输入一个字符 $opt$ 和两个整数 $x,y$。
若 $opt=$A，插入一个节点，其编号为当前存在的节点数量（包括当前新加入的节点），其父节点为 $x$，边权为 $y$。（$0 \le y \le 2^{30}$，数据确保 $x$ 为之前已插入的节点编号）。
若 $opt=$Q，查询起点为 $x$ 号节点，终点在 $y$ 的子树中的最大简单路径异或和（数据确保 $x,y$ 为已存在的节点编号，且至少存在一条合法的简单路径使得起点与终点不同。换言之，当 $x=y$ 时，数据确保 $x$ 不为当前的叶子节点）。
若干行，对于每次查询操作，输出一行，一个整数，表示要求的最大路径异或和。
4 A 1 2 Q 1 1 A 1 3 Q 1 1
2 3