题目背景

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$ 行包含两个数 $n, q$，分别表示人数和询问次数。

第 $2$ 行包含 $n-1$ 个数 $f_{2 \dots n}$，其中 $f_i$ 表示 $i$ 的父亲。

第 $3$ 行包含 $n$ 个数 $a_{1 \dots n}$，其中 $a_i$ 表示 $i$ 的智商值。

接下来 $q$ 行每行两个或三个数表示一个合法询问，其中第一个数表示询问种类，后面一个或两个数为询问参数。

输出格式

输出 $q$ 行，每行一个数表示询问的答案。

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

5
2
1
3
4
3
1
3
2
4
5

提示

【样例说明】

形成的树如下：

首先比较编号为 $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。