题目描述

现在有一棵树，初始时只有一个根节点 $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 的操作，输出一行表示答案，保证至少有一次这样的操作。

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$。

说明

题目译自 CEOI 2011 day 1 T3 Treasure Hunt。