题目描述

JOI 王国由 $N$ 个城市组成，编号为 $1$ 到 $N$。有 $N - 1$ 条单向道路连接这些城市。具体来说，对于每个 $i = 2, 3, \dots, N$，都有一条从城市 $i$ 通往城市 $P_i$ 的道路。这里保证 $1 \le P_i < i$。

每个城市都有一个定义的危险等级。首都城市（城市 $1$）的危险等级为 $0$。对于城市 $i$ ($2 \le i \le N$)，其危险等级定义为从城市 $i$ 到城市 $1$ 的路径上所经过的道路数量。由于 JOI 王国的结构，从任意城市 $i$ 到城市 $1$ 都有且仅有一条唯一路径。

目前，城市 $i$ ($1 \le i \le N$) 中居住着 $K_i$ 只海狸。JOI 王国的总统 Bitaro 制定了一项海狸迁移计划。该迁移计划将在 $Q$ 天内执行。在第 $j$ 天 ($1 \le j \le Q$)，会发生以下三种事件之一：

• 迁移 (Relocation)：此时居住在危险等级为 $X_j$ 的城市中的所有海狸，将移动到危险等级为 $Y_j$ 的城市，它们可以通过从当前城市出发沿一条或多条道路到达该城市。保证 $0 \le Y_j < X_j$。由于 JOI 王国的结构，每只海狸的迁移目的地是唯一确定的。
• 移民 (Immigration)：由于来自 JOI 王国外部的移民，城市 $A_j$ 中居住的海狸数量增加了 $L_j$。
• 调查 (Survey)：调查当前居住在城市 $B_j$ 中的海狸数量。

作为 Bitaro 的下属，你意识到你可以在不亲自访问城市的情况下，仅根据迁移计划的信息计算出每次调查事件中的海狸数量。

给定 JOI 王国的结构、每个城市当前居住的海狸数量以及迁移计划的详细信息，编写一个程序来计算每次调查事件的结果。

输入格式

从标准输入读取以下数据。

$N$ $P_2 \ P_3 \ \dots \ P_N$ $K_1 \ K_2 \ \dots \ K_N$ $Q$ (Query 1) (Query 2) $\vdots$ (Query $Q$)

每个 (Query $j$) ($1 \le j \le 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 \le j \le Q$)，按顺序每行输出一个整数，表示当时城市 $B_j$ 中的海狸数量。

数据范围

• $2 \le N \le 2\,000\,000$。
• $1 \le P_i < i$ ($2 \le i \le N$)。
• $0 \le K_i \le 100$ ($1 \le i \le N$)。
• $1 \le Q \le 2\,000\,000$。
• $T_j$ 为 $1, 2$ 或 $3$ ($1 \le j \le Q$)。
• 如果 $T_j = 1$，则 $0 \le Y_j < X_j \le N - 1$ ($1 \le j \le Q$)。
• 如果 $T_j = 2$，则 $1 \le A_j \le N, 1 \le L_j \le 100$ ($1 \le j \le Q$)。
• 如果 $T_j = 3$，则 $1 \le B_j \le N$ ($1 \le j \le Q$)。
• 至少有一个 $j$ ($1 \le j \le Q$) 满足 $T_j = 3$。
• 所有输入值均为整数。

子任务

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

1. (4 分) $D = 1$。
2. (8 分) $N \le 20$。
3. (13 分) $D \le 20$。
4. (15 分) 没有查询满足 $T_j = 2$，且最多有 5 个查询满足 $T_j = 3$。
5. (15 分) 最多有 5 个查询满足 $T_j = 3$。
6. (27 分) 没有查询满足 $T_j = 2$。
7. (18 分) 无附加限制。

样例

样例 1

输入：

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

样例 2

输入：

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

样例 3

输入：

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