题目背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

新入职西西艾弗岛有限公司的小 C 接替了刚刚升职的小 S 的项目。然而小 C 打开项目工程时，一层层嵌套的文件夹让小 C 感到眼花缭乱。为了精简项目结构，小 C 决定对项目的文件夹进行一些必要的合并。

项目中共有 $n$ 个文件夹。为了方便，我们用 $1$ 至 $n$ 的整数给这 $n$ 个文件夹编号，其中编号为 $1$ 的文件夹为项目的根文件夹，其他每个文件夹都有一个父文件夹，这些文件夹构成了树形结构。除了子文件夹以外，第 $i$ 个文件夹内还直接存储了 $d_i$ 字节的数据。

小 C 进行了若干次文件夹合并操作。每次操作中小 C 会选择一个文件夹 $x_j$，将这个文件夹和它的所有子文件夹合并。具体地，小 C 会进行以下操作：遍历 $x_j$ 的子文件夹 $y$，将文件夹 $y$ 包含的所有文件夹和文件移动到文件夹 $x_j$，然后删除文件夹 $y$。所有文件和文件夹的名称是两两不同的，合并过程中不需要考虑文件或文件夹重名的情况。在每一次合并操作后，小 C 需要知道文件夹 $x_j$ 内共有几个文件夹以及多少字节的数据。

例如，考虑以下项目：根文件夹内有文件夹 $2$ 和文件夹 $3$ 以及 $100$ 字节数据，其中文件夹 $2$ 为空文件夹，文件夹 $3$ 内有 $200$ 字节数据和文件夹 $4$，文件夹 $4$ 包含 $300$ 字节数据。对根文件夹进行一次合并后，文件夹 $2$ 和文件夹 $3$ 被合并至根文件夹，此时根文件夹下有文件夹 $4$ 以及 $300$ 字节数据，而文件夹 $4$ 下也包含 $300$ 字节数据。

在合并文件夹的过程中，小 C 常常需要访问某个文件夹 $z_j$ 下的文件。此时，小 C 会从根文件夹开始，每次进入当前文件夹的一个子文件夹。小 C 需要知道按照以上过程，获取到文件夹 $z_j$ 下的文件至少需要经过多少个文件夹。

例如，在以上项目中，未对根文件夹进行合并前，访问根文件夹下的文件只需要经过根文件夹一个文件夹，而访问文件夹 $4$ 则需要经过根文件夹以及文件夹 $3$ 和 $4$。而对根文件夹进行合并之后，访问文件夹 $4$ 只需要经过根文件夹和文件夹 $4$ 了。

在整个项目中，小 C 一共进行了 $m$ 次文件夹合并以及文件访问操作。你需要帮助小 C 正确维护文件夹之间的关系，并在每次操作后正确回答小 C 需要的数据。

输入格式

从标准输入读入数据。

输入的第一行两个整数 $n, m$，分别表示文件夹数量以及操作次数。

第二行 $(n - 1)$ 个整数 $f_2, \cdots , f_n$，其中 $f_i$ 表示文件夹 $i$ 的父文件夹编号。

第三行 $n$ 个整数 $d_1, d_2, \cdots , d_n$，其中 $d_i$ 表示文件夹 $i$ 中数据的存储量。

接下来 $m$ 行第 $j$ 行两个整数，第一个整数 $op_j$ 表示操作类型。若 $op_j = 1$ 则表示一次文件夹合并操作，接下来一个整数 $x_j$ 表示合并的文件夹编号；若 $op_j = 2$ 则表示一次文件访问操作，接下来一个整数 $z_j$ 表示访问的文件夹编号。

输出格式

输出到标准输出。

输出 $m$ 行，第 $j$ 行表示第 $j$ 个操作中小 C 需要的数据：若 $op_j = 1$ 则输出两个整数，依次表示文件夹 $x_j$ 的子文件夹数量以及数据的存储量；若 $op_j = 2$ 则输出一个整数表示小 C 获取文件夹 $z_j$ 下的数据最少需要经过的文件夹个数。

4 6
1 1 3
100 0 200 300
2 1
2 4
1 1
2 4
1 1
1 1

1
3
1 300
2
0 600
0 600

提示

子任务

对于所有测试数据，

• $1 \le n \le 5 \times 10^5, 1 \le m \le 3 \times n$,
• $1 \le f_i \le n$，输入的文件夹结构构成树形结构，
• $0 \le d_i \le 10^5$,
• $1 \le x_j, z_j \le n$，每次合并操作中给出的文件夹 $x_j$ 没有被删除，每次文件访问操作中给出的文件夹 $z_j$ 没有被删除。

子任务编号	$n \le$	特殊性质	分值
1	500	无	10
2	5,000	^	15
3	$10^5$		^
4	$5 \times 10^5$	A	5
5	^	B	^
6		C	10
7		D	15
8		E	10
9		无	15

特殊性质 A：$f_i = (i - 1)$。

特殊性质 B：$f_i = 1$。

特殊性质 C：在文件夹合并操作中，$x_j = 1$。

特殊性质 D：$op_j = 1$，即没有文件访问操作。

特殊性质 E：$op_j = 2$，即没有文件夹合并操作。