树上倍增

题目描述

现有一棵树。您需要写一个树上倍增算法，以实现如下操作：

• A x 新建一个节点，将它作为x节点的儿子，编号为当前节点总数+1。
• Q k p1 p2 p3.... 查询p1,p2,p3...这些节点的LCA。其中k表示查询节点的个数。

最初树上只有一个节点，编号为1。
多个节点的LCA定义为：这些节点的公共祖先中深度最大的。

输入格式

第一行，一个正整数$n$，表示操作个数。
接下来$n$行，每行输入一个操作，格式如题目描述所述。

保证任何输入的数都是正整数。

输出格式

对于每一个Q操作，输出一行一个正整数，表示所询问节点的LCA。

样例数据

样例输入

7
A 1
A 2
A 3
A 1
A 5
A 5
Q 2 3 6
Q 2 6 7
Q 2 4 2
Q 3 7 6 5

样例输出

1
5
2
5

解释

3,6的LCA是1。
6,7的LCA是5。
4,2的LCA是2。
7,6,5的LCA是5。

数据规模与约定

对于$20\%$的数据，有$n \leq 100,k=2$。

对于$40\%$的数据，有$n \leq 100000,k\leq 10$。

对于$100\%$的数据，有$n \leq 1000000,k\leq 1000$。

保证询问不超过$1000$次。