C1564 【XR-1】柯南家族

xht37 最近沉迷于名侦探柯南。

在某集中，小兰又在怀疑柯南的真实身份了。为了让小兰不再怀疑，柯南编造出自己的家族背景来应对小兰的询问。

这个家族一开始只有一个人，后来不断有人有了孩子，直到现在，这个家族有 $n$ 个人，第 $n$ 个人正是柯南。易知这个家族构成了一个 $n$ 个点的树形结构。

柯南为了使自己编造的家庭背景更加真实，他给家族中的每个人赋予了一个智商值。但是，一个人的聪明程度不仅仅只与他的智商值有关，还可能与他祖先的聪明程度及他出生的时代有关。

具体来说，在这个家族中，A 比 B 聪明当且仅当 A 和 B 满足下面三种情况中的某一种：

1. A 的智商值比 B 的智商值高；
2. A 的智商值与 B 的智商值一样且 A 和 B 有不同的父亲，A 的父亲比 B 的父亲聪明；
3. A 的智商值与 B 的智商值一样且 A 和 B 的父亲是同一个人或某一个人没有父亲，A 比 B 后出生。

有一个很显然的结论是，这个家族中不会有两个人一样聪明。

柯南需要回答小兰的 $q$ 个询问。为了方便说明，假设第 $i$ 个出生的人编号为 $i$。

每个询问是下面三种情况中的某一种：

1. 1 x：询问编号为 $x$ 的人在整个家族中聪明程度排第几。

2. 2 x k：询问编号为 $x$ 的人及其祖先中第 $k$ 聪明的人的编号。

3. 3 x k：询问编号为 $x$ 的人及其后代中第 $k$ 聪明的人的编号。

柯南还有许多案子要办，他不想在回答小兰的问题上浪费时间，他希望你能编程帮他回答小兰的所有询问。

样例输入 1

5 11
1 1 3 2
1 2 2 1 1
1 1
1 2
1 3
1 4
1 5
2 4 1
2 5 3
3 1 1
3 1 2
3 1 3
3 1 4

样例输出 1

5
2
1
3
4
3
1
3
2
4
5