C. 逆向生长

你平时会怎样画一棵树？我想你会先画出根节点，接着向下延伸出几条边，连向它的儿子节点，然后继续向下，画出孙子节点……

如果这一切颠倒过来，会发生什么？

现在你有一棵逆向生长的树，这棵树有 个叶子节点，编号依次为 。一开始，你只有这 个叶子节点，你将依次处理 个操作，操作 分为如下两种：

• ：表示新增一个节点 ，它有 个儿子，分别为 ，由于树是逆向生长的，此时 的儿子节点都已经存在；
• ：表示一次询问，求出 在树上的 LCA（最近公共祖先节点），如果此时 不连通，请输出 0。

注意：在 次操作之后，所有节点不一定连通。

本题输入采用强制在线，具体细节请见【输入格式】。

第一行一个整数 （）表示树叶子节点的个数。假设这棵树一共有 （）个节点。

第二行 个整数，（）。

第三行一个整数 （，），表示操作个数， 为计算系数。定义函数 ，其中 为上次 的操作输出的答案，初始情况 。

接下来 行，每行表示一个操作，其中第 行第一个数为 ：

• 若 ，则接下来为两个整数 （），然后为 个整数 ；
  • 该操作为新增一个节点，其编号为 ；
  • 表示 的儿子节点的个数；
  • 的儿子节点为 ，其中 ；
• 若 ，则接下来为两个整数 ；
  • 该操作为询问 当前的 LCA 节点编号，其中 ；
  • 如果此时 不连通，请输出 0；
  • 设当前询问的输出结果为 ，则当前操作之后，将 修改为 。

对于所有输入中的 等，保证其取值范围为 。

对于每个 的询问，输出一行，其中包含一个整数，表示该询问的答案。

样例输入

4
4 10 7 5
10 1 0
1 2 1 7
2 10 4
1 3 1 2
1 1 4 4 10 3 5
2 7 7
1 9 1 1
2 9 10
1 8 1 9
1 6 1 8
2 6 7

样例输出

0
7
9
6

对于 30% 的数据：；

对于 50% 的数据：；

另有 25% 的数据：。（即 ，那么 ，可以发现，该部分输入不强制在线）；

对于 100% 的数据：。

提示：由于输出量过大，请不要使用过慢的输入输出方式（如未关同步的 cin/cout）。