P7543 [CEOI 2011] Treasure Hunt

现在有一棵树，初始时只有一个根节点 $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++ 中，使用 fflush(stdout) 或 cout.flush()。 - 在 Pascal 中，使用 flush(output)。 - 在 Python 中，使用 stdout.flush()。 - 其它语言请自行查阅文档。

对于每一次 `D u v` 的操作，输出一行表示答案，保证至少有一次这样的操作。

对于 $20\%$ 的数据，保证最终点的编号最大不超过 $5000$，且 $n\le 5000$； 对于 $50\%$ 的数据，保证最终点的编号最大不超过 $400\ 000$； 对于 $100\%$ 的数据，保证最终点的编号最大不超过 $10^9$，且 $n\le 400\ 000$。 #### 说明 题目译自 [CEOI 2011 day 1 T3 _Treasure Hunt_](http://ceoi.inf.elte.hu/probarch/11/trezad.pdf)。