【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$ 行包含两个数 $n, q$,分别表示人数和询问次数。 第 $2$ 行包含 $n-1$ 个数 $f_{2 \dots n}$,其中 $f_i$ 表示 $i$ 的父亲。 第 $3$ 行包含 $n$ 个数 $a_{1 \dots n}$,其中 $a_i$ 表示 $i$ 的智商值。 接下来 $q$ 行每行两个或三个数表示一个合法询问,其中第一个数表示询问种类,后面一个或两个数为询问参数。

输出格式


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

输入输出样例

输入样例 #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

说明

【样例说明】 形成的树如下: ![](https://cdn.luogu.com.cn/upload/pic/57742.png) 首先比较编号为 $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。