Source : 北京大学邓哲也
Description

小Z手里有很多很多三维弹球,为了把它们收集起来,她设计了一个容器。

这个容器可以看作一个有根树的结构,每个节点的标号为从1到n。每个节点可以是空的或者可以容纳一个弹球。一开始,所有节点都是空的。

当小Z开始收集弹球的时候,可能会产生以下两种操作:

1. 往容器中依次放 x 个球。球被依次放进根节点,只要这个球的下方有空节点,它就会往下掉落。如果有多个空节点,那么球会选择子树中的最小节点编号最小的子节点掉落。所以如果一个球往下掉落多次,它将会在第一层做一次选择。比如我们往下图这个容器中放两个球,它们将依次落在1号和3号节点上。第一个球从4号落到了3号,因为3号是空的,且以3号节点为根的子树中最小节点编号是1(比2更小),然后它从3号落到了1号节点。第二个球从4号落到3号,然后停住了。

2. 从 x 号节点上拿走球。因为小 Z 在整理的过程中发现 x 号节点上的球很好玩,于是把它拿了出来,这就会导致它上面的球(如果有的话)可能会往下掉落。只要一个空节点的父亲节点有球,那么这个球就会向下掉落。比如我们从下图容器中依次取走5号、7号和8号节点的球,最终1号、2号和3号节点将变为空节点。移走5号节点的球时,3号、2号和1号节点的球依次掉落;移走6号节点的球时,3号和2号节点的球依次掉落;移走8号节点时,6号和3号节点的球依次掉落。

Input

第一行包含三个整数 n,q 和testID,分别表示树的节点个数、操作数和测试点编号。

第二行包含 n 个整数 fi,表示 i 的父亲节点。如果 fi = 0,说明 i 是根节点。

接下来 q 行,每行两个数 type 和 x,意义见题目描述。

输入数据保证所有操作均合法,即加入球的个数不会超过空位的个数,也不会从一个空节点移除球。

Output

对于每个操作 1,输出最后一个加入的球所在的位置;

对于每个操作 2,输出移除该球后会引起多少个球下落。

Sample Input
8 4 0
0 1 2 2 3 3 4 6
1 8
2 5
2 7
2 8
Sample Output
1
3
2
2
Hint

样例解释

加入 8 个球所以第 8 个球的位置是 1 号节点,剩下三个操作 2 的解释见题面描述。

数据规模与约定

记特征 A 表示“只有一次操作 1”,特征 B 表示“操作 2 不会造成球的下落”

“随机构造”的树是指对于 i(i > 1) 号节点,i 的父亲节点从 [1, i − 1] 中等概率随机选取