P5346 【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$ 聪明的人的编号。 柯南还有许多案子要办，他不想在回答小兰的问题上浪费时间，他希望你能编程帮他回答小兰的所有询问。

无

无

【样例说明】 形成的树如下：  首先比较编号为 $2,3$ 的两个人，由于** $3$ 号的智商值与 $2$ 号的智商值一样且他们的父亲是同一个人，$3$ 号比 $2$ 号后出生**满足第 $3$ 种情况，因此 $3$ 号比 $2$ 号聪明。 再比较编号为 $4,5$ 的两个人，由于** $4$ 号的智商值与 $5$ 号的智商值一样且他们有不同的父亲，$4$ 号的父亲 $3$ 号比 $5$ 号的父亲 $2$ 号聪明**满足第 $2$ 种情况，因此 $4$ 号比 $5$ 号聪明。 再比较编号为 $1,5$ 的两个人，由于** $5$ 号的智商值与 $1$ 号的智商值一样且 $1$ 号没有父亲，$5$ 号比 $1$ 号后出生**满足第 $3$ 种情况，因此 $5$ 号比 $1$ 号聪明。 再根据第 $1$ 种情况比较编号为 $2,4$ 的两个人，可对 $5$ 人的聪明程度排序：$3 > 2 > 4 > 5 > 1$。 【数据规模与约定】 一共 $10$ 个测试点。 对于前 $20\%$ 的数据，$1 \le n, q \le 10 ^ 3$，每个测试点 $7$ 分，时限 1s。 对于另 $20\%$ 的数据，保证一个人最多只有一个儿子，每个测试点 $9$ 分，时限 4s。 对于另 $20\%$ 的数据，$1 \le n, q \le 10 ^ 5$，每个测试点 $9$ 分，时限 1.5s。 对于另 $20\%$ 的数据，保证只有第一种询问，每个测试点 $12$ 分，时限 1.5s。 对于 $100\%$ 的数据，$1 \le n, q \le 5 \times 10 ^ 5$，$1 \le a_i \le 10 ^ 9$，每个测试点 $13$ 分，时限 2.5s。