4493: 「CEOI2011」Treasure Hunt
内存限制：256 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
现在有一棵树，初始时只有一个根节点 $1$，你需要完成下列两种操作：
* `path u s` 表示在 $u$ 下面依次加入了 $s$ 个节点：其中的第 $i$ 个节点作为第 $i-1$ 个节点的孩子（$2\le i\le s$），特别地，第 $1$ 个节点会作为 $u$ 的孩子。设加入前时，树中节点的最大编号为 $n$，则新加入的 $s$ 个点会被依次编号为 $n+1,n+2,\cdots,n+s$；
* `dig u v` 表示询问 $u,v$ 的中点。形式化地，设 $u,v$ 间的距离为 $d$，则你需要求出 $u,v$ 的路径上，距离 $u$ 为 $\lfloor \frac d2\rfloor$ 的节点编号。
输入
本题是一道交互题，首先你需要从标准输入读入操作次数 $n$。
接下来 $n$ 次，你会得到以下两种格式的指令之一：
* `P u s` 表示一次 `path u s` 的操作；
* `D u v` 表示一次 `dig u v` 的操作。
对于第一种操作，你不需要输出任何东西。对于第二种操作，你必须给出答案并清空缓冲区后（`C/C++` 中的 `fflush(stdout)`），才可以读取后续操作。
输出
对于每一次 `D u v` 的操作，输出一行表示答案，保证至少有一次这样的操作。
样例输入 复制
11
P 1 2
D 1 3
P 2 5
D 7 3
D 3 7
P 1 2
P 3 3
D 10 11
P 5 1
D 14 8
D 2 4样例输出 复制
2
5
4
1
6
2提示
数据范围：对于 $20\%$ 的数据，保证最终点的编号最大不超过 $5000$，且 $n\le 5000$； 对于 $50\%$ 的数据，保证最终点的编号最大不超过 $400\ 000$； 对于 $100\%$ 的数据，保证最终点的编号最大不超过 $10^9$，且 $n\le 400\ 000$。