我们有一个可以形象地看作一棵有根树的“滚球机”。树上的节点编号为 $1$ 到 $N$。每个节点要么是空的，要么包含一个球。最初，所有节点都是空的。在运行过程中，该机器可以执行两种不同类型的操作：

1. 向滚球机中添加 $k$ 个球：球被逐个放入根节点。只要一个球的下方直接连接着空的子节点，它就会向下滚动。如果有多个空的子节点，球会选择其子树中含有编号最小的节点的那一个子节点。因此，如果球向下滚动多层，它会在每一层都做出选择。例如：如果我们向图中的机器添加两个球，它们将落入节点 $1$ 和 $3$：第一个球从节点 $4$ 滚动到节点 $3$，因为节点 $3$ 是空的，且其子树（由节点 $3$ 和 $1$ 组成）中包含节点 $1$；它接着从节点 $3$ 滚动到节点 $1$。第二个球同样从节点 $4$ 滚动到节点 $3$ 并停留在那里。

1. 从指定节点中取出球：该节点变为空，上方的球（如果有的话）会向下滚动。每当一个空节点的父节点包含球时，这个球就会向下滚动。如果我们从下图所示的机器中依次取出节点 $5$、$7$ 和 $8$ 中的球，节点 $1$、$2$ 和 $3$ 将变为空。

输入格式

第一行包含两个整数 $N$ 和 $Q$ —— 树的节点数和操作数。

接下来的 $N$ 行描述滚球机。这些行中的每一行包含一个整数，表示节点的编号：其中第 $i$ 行包含节点 $i$ 的父节点编号，如果节点 $i$ 是树根，则为 $0$。

接下来的 $Q$ 行，每行包含两个整数，描述要执行的操作。

• 类型 1 的操作用 1 k 表示，其中 $k$ 是要添加到机器中的球数。
• 类型 2 的操作用 2 x 表示，其中 $x$ 是要取出球的节点编号。

保证所有执行的操作都是合法的：操作不会要求添加超过滚球机中空节点数量的球，也不会要求从空节点中取出球。

输出格式

对于每个类型 1 的操作，输出最后一个放入的球最终落入的节点编号。

对于每个类型 2 的操作，输出在从指定节点取出球后，向下滚动的球的数量。

数据范围

始终满足 $N, Q \le 100\,000$。

• 在价值 25 分的测试点中，每个节点有 0 个或 2 个子节点。此外，所有没有子节点的节点到根节点的距离都相同。
• 在价值 30 分的测试点中，操作的给定方式保证在执行类型 2 的操作后，永远不会有球向下滚动。
• 在价值 40 分的测试点中，恰好只有一次类型 1 的操作，且它是最开始的第一次操作。

这三组测试点两两不相交。

样例

输入样例 1

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

输出样例 1

1
3
2
2