最开始，树中只有一个节点，编号为 $1$，代表树的根。你的任务是支持 $Q$ 次以下格式的操作：
Add x y— 在树中添加一个新节点作为节点 $x$ 的儿子。新添加的节点与节点 $x$ 之间由一条权值为 $y$ 的边相连。新添加的节点的编号等于添加后树中节点的总数。Query a b— 在树中寻找一条最长路径，该路径以节点 $a$ 为起点，以节点 $b$ 的子树中的某个节点（节点 $b$ 自身也属于其子树）为终点。路径的长度定义为该路径上所有边权值的异或（xor）和。
输入格式
第一行包含一个整数 $Q$ ($1 \le Q \le 200\,000$)，表示操作次数。
接下来的 $Q$ 行中，第 $i$ 行包含第 $i$ 个操作，其格式与题目描述中的操作之一相对应。值 $x$、$a$ 和 $b$ 在操作时都指向当时已存在的节点，且值 $y$ 不大于 $2^{30}$。
输出格式
对于每个 Query 类型的操作，输出一个对应的答案。每个答案应在单独的一行中输出，输出顺序与输入中对应询问出现的顺序一致。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 11 | $Q \le 200$ |
| 2 | 22 | $Q \le 2\,000$ |
| 3 | 33 | 对于所有 Query 类型的操作，均满足 $b = 1$ |
| 4 | 44 | 无附加限制 |
样例
输入样例 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