题目背景

本题测试点极大，评测时可能需要等待较长时间加载测试点。

题目描述

JOI 王国由编号从 $1$ 到 $N$ 的 $N$ 个城市组成。这些城市通过 $N − 1$ 条单向道路连接。具体来说，对于每个 $i = 2, 3, \ldots, N$，存在一条从城市 $i$ 通向城市 $P_i$ 的道路。此处保证 $1 \leq P_i < i$。

每个城市有一个定义好的危险等级。首都（城市 $1$）的危险等级为 $0$。对于城市 $i$（$2 \leq i \leq N$），其危险等级定义为从该城市到城市 $1$ 的路径中经过的道路数量。根据 JOI 王国的结构，从任意城市 $i$ 到城市 $1$ 的路径存在且唯一。

当前，城市 $i$（$1 \leq i \leq N$）居住着 $K_i$ 只海狸。JOI 王国的总统 Bitaro 计划实施海狸迁移计划。该计划将在 $Q$ 天内执行。在第 $j$ 天（$1 \leq j \leq Q$），以下三类事件之一会发生：

• 迁移：当时刻所有居住在危险等级为 $X_j$ 的城市的海狸会迁移到危险等级为 $Y_j$ 的城市，该城市需满足从当前城市出发沿道路行进可达。保证 $0 \leq Y_j < X_j$。根据 JOI 王国的结构，每只海狸的迁移目的地唯一确定。
• 迁入：由于王国外的迁入，城市 $A_j$ 的海狸数量增加 $L_j$。
• 调查： 调查当前时刻城市 $B_j$ 居住的海狸数量。

作为 Bitaro 的下属，你发现无需实地考察即可根据迁移计划信息计算出每次调查事件时的海狸数量。

给定 JOI 王国的结构、各城市当前的海狸数量及迁移计划详情，请编写程序计算每次调查事件的结果。

输入格式

$N$
$P_2$ $P_3$ $\cdots$ $P_N$
$K_1$ $K_2$ $\cdots$ $K_N$
$Q$
（查询 $1$）
（查询 $2$）
$\vdots$
（查询 $Q$）

每个（查询 $j$）（$1 \leq j \leq Q$）由若干空格分隔的整数组成。首个整数为 $T_j$，后续内容如下：

• 若 $T_j = 1$，该行后续有两个整数 $X_j$, $Y_j$。表示第 $j$ 天发生迁移事件，所有当时危险等级为 $X_j$ 的城市的海狸迁移到危险等级为 $Y_j$ 的可达城市。
• 若 $T_j = 2$，该行后续有两个整数 $A_j$, $L_j$。表示第 $j$ 天发生迁入事件，城市 $A_j$ 的海狸数量增加 $L_j$。
• 若 $T_j = 3$，该行后续有一个整数 $B_j$。表示第 $j$ 天发生调查事件，调查当前城市 $B_j$ 的海狸数量。

输出格式

对于每个满足 $T_j = 3$ 的 $j$（$1 \leq j \leq Q$），按顺序逐行输出当时城市 $B_j$ 的海狸数量。

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

1
8
0
3

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

3
13
0
4
0
17

7
1 2 1 3 3 2
5 2 8 9 4 0 5
10
1 3 1
2 4 10
3 2
1 6 3
1 2 0
3 1
3 4
2 5 6
3 5
3 3

6
18
19
6
0

提示

样例解释

样例 $1$ 解释

初始时，城市 $1$, $2$, $3$, $4$ 分别有 $1$, $3$, $4$, $3$ 只海狸。这些城市的危险等级分别为 $0$, $1$, $1$, $2$。

• 第 $1$ 天发生调查事件。第一行输出 $1$，表示城市 $1$ 的海狸数量。
• 第 $2$ 天发生迁移事件。城市 $2$ 和 $3$ 的海狸全部迁移到城市 $1$。第 $2$ 天结束时，城市 $1$, $2$, $3$, $4$ 分别有 $8$, $0$, $0$, $3$ 只海狸。
• 第 $3$ 天发生调查事件。第二行输出 $8$。
• 第 $4$ 天发生调查事件。第三行输出 $0$。
• 第 $5$ 天发生迁移事件。城市 $4$ 的海狸全部迁移到城市 $2$。第 $5$ 天结束时，城市 $1$, $2$, $3$, $4$ 分别有 $8$, $3$, $0$, $0$ 只海狸。
• 第 $6$ 天发生调查事件。第四行输出 $3$。

该样例满足子任务 $2\sim 7$ 的限制。

样例 $2$ 解释

初始时，城市 $1$, $2$, $3$ 分别有 $3$, $1$, $4$ 只海狸。这些城市的危险等级分别为 $0$, $1$, $1$。

• 第 $1$ 天发生迁入事件。城市 $2$ 的海狸数量增加 $5$。第 $1$ 天结束时，城市 $1$, $2$, $3$ 分别有 $3$, $6$, $4$ 只海狸。
• 第 $2$ 天发生迁移事件。无海狸迁移，因为不存在危险等级为 $2$ 的城市。
• 第 $3$ 天发生调查事件。第一行输出 $3$。
• 第 $4$ 天发生迁移事件。城市 $2$ 和 $3$ 的海狸全部迁移到城市 $1$。第 $4$ 天结束时，城市 $1$, $2$, $3$ 分别有 $13$, $0$, $0$ 只海狸。
• 第 $5$ 天发生调查事件。第二行输出 $13$。
• 第 $6$ 天发生调查事件。第三行输出 $0$。 后续事件类似发生，此处省略具体描述。

该样例满足子任务 $1\sim 3,7$ 的限制。

样例 $3$ 解释

该样例满足子任务 $2,3,5,7$ 的限制。

数据范围

• $2 \leq N \leq 2\,000\,000$。
• $1 \leq P_i < i$（$2 \leq i \leq N$）。
• $0 \leq K_i \leq 100$（$1 \leq i \leq N$）。
• $1 \leq Q \leq 2\,000\,000$。
• $T_j$ 的取值为 $1$, $2$ 或 $3$（$1 \leq j \leq Q$）。
• 若 $T_j = 1$，则 $0 \leq Y_j < X_j \leq N − 1$（$1 \leq j \leq Q$）。
• 若 $T_j = 2$，则 $1 \leq A_j \leq N$，$1 \leq L_j \leq 100$（$1 \leq j \leq Q$）。
• 若 $T_j = 3$，则 $1 \leq B_j \leq N$（$1 \leq j \leq Q$）。
• 至少存在一个 $j$（$1 \leq j \leq Q$）满足 $T_j = 3$。
• 所有输入值为整数。

子任务

设城市最大危险等级为 $D$。

• $\text{Subtask 1 (4 pts)}$：$D = 1$。
• $\text{Subtask 2 (8 pts)}$：$N \leq 20$。
• $\text{Subtask 3 (13 pts)}$：$D \leq 20$。
• $\text{Subtask 4 (15 pts)}$：不存在 $T_j = 2$ 的查询，且最多有 $5$ 个 $T_j = 3$ 的查询。
• $\text{Subtask 5 (15 pts)}$：最多有 $5$ 个 $T_j = 3$ 的查询。
• $\text{Subtask 6 (27 pts)}$：不存在 $T_j = 2$ 的查询。
• $\text{Subtask 7 (18 pts)}$：无额外限制。