题目背景

滥用本题评测将封号。

题目描述

众所周知，一个公司的 $n$ 个部门可以组织成一个树形结构。形式化地，假设这些部门依次编号为 $1, \ldots, n$，那么除了 $1$ 号部门以外，第 $i \in [2, n]$ 个部门有且仅有一个上级部门 $p_i \in [1, i - 1]$。这样，这家公司的 $n$ 个部门可以视为一个以 $1$ 为根的树。如果 $i$ 是 $j$ 子树中的点，那么称部门 $i$ 是部门 $j$ 的子部门。

该公司初始时有 $k$ 名优秀员工，编号依次为 $1 \ldots k$。第 $i$ 名优秀员工初始时在第 $x_i$ 个部门工作，并且其有一个能力值 $v_i > 0$。

为了最大化公司的运作效率，公司老板 0/\/\G 决定进行一些人员调动。具体来说，可以将编号为 $i$ 的优秀员工调动到 $x_i$ 的一个子部门，或者不调度（此时该员工在 $x_i$ 部门）。随后，优秀员工们会在其所在的部门竞选部门领导——能力值最高者将担任这一职位，并给公司带来等同于其能力值的贡献。如果一个部门一个优秀员工也没有，那么就无法选出部门领导，从而对公司的贡献将是 $0$。此时，公司的业绩被定义为公司各部门的贡献之和。

公司老板 0/\/\G 自然想知道，该如何进行人员调动，使公司的业绩最大？

这当然难不倒他，然而，公司优秀员工的数量也会发生变化；具体来说，会依次发生 $m$ 个事件，每个事件形如：

• 1 x v：先令 $k = k + 1$，然后新增一位编号为 $k$、初始部门为 $x$、能力值为 $v$ 的优秀员工；
• 2 id：编号为 $\mathit{id}$ 的优秀员工将被辞退。

公司老板 0/\/\G 希望你能在最开始和每个事件发生后，告诉他公司的业绩最大可能是多少？

注意，每次人员调动都是独立的，也就是每次计算公司的最大可能业绩时，每个优秀员工都会回到其所在的初始部门。

输入格式

输入的第一行包含一个正整数 $\mathit{sid}$，表示该测试点对应的数据范围以及特殊性质，详见后表；

输入的第二行包含三个整数 $n, k, m$，分别表示部门数，初始优秀员工数和事件数。

输入的第三行包含 $n - 1$ 个正整数 $p_2, \ldots, p_n$，表示每个部门的上级部门。

接下来 $k$ 行，每行包含两个正整数 $x_i, v_i$，表示优秀员工的初始部门和能力值。

接下来 $m$ 行，每行形如 1 x v 或 2 id 表示一次事件。

输出格式

输出一行包含 $m + 1$ 个由单个空格隔开的非负整数，依次表示最开始和每个事件发生后，公司的业绩可能的最大值。

输入输出样例 #1

1
3 2 1
1 1
2 1
1 3
1 2 2

4 5

输入输出样例 #2

见附件中的 transfer/transfer2.in

见附件中的 transfer/transfer2.ans

输入输出样例 #3

见附件中的 transfer/transfer3.in

见附件中的 transfer/transfer3.ans

输入输出样例 #4

见附件中的 transfer/transfer4.in

见附件中的 transfer/transfer4.ans

输入输出样例 #5

见附件中的 transfer/transfer5.in

见附件中的 transfer/transfer5.ans

输入输出样例 #6

见附件中的 transfer/transfer6.in

见附件中的 transfer/transfer6.ans

输入输出样例 #7

见附件中的 transfer/transfer7.in

见附件中的 transfer/transfer7.ans

输入输出样例 #8

见附件中的 transfer/transfer8.in

见附件中的 transfer/transfer8.ans

输入输出样例 #9

见附件中的 transfer/transfer9.in

见附件中的 transfer/transfer9.ans

输入输出样例 #10

见附件中的 transfer/transfer10.in

见附件中的 transfer/transfer10.ans

输入输出样例 #11

见附件中的 transfer/transfer11.in

见附件中的 transfer/transfer11.ans

输入输出样例 #12

见附件中的 transfer/transfer12.in

见附件中的 transfer/transfer12.ans

输入输出样例 #13

见附件中的 transfer/transfer13.in

见附件中的 transfer/transfer13.ans

输入输出样例 #14

见附件中的 transfer/transfer14.in

见附件中的 transfer/transfer14.ans

输入输出样例 #15

见附件中的 transfer/transfer15.in

见附件中的 transfer/transfer15.ans

说明/提示

【数据范围】

对于所有的数据，保证：$1 \le \mathit{sid} \le 15$，$1 \le n, k \le 10^5$，$0 \le m \le 10^5$，$1 \le p_i < i$，$1 \le x_i, x \le n$，$1 \le v_i, v \le 10^5$。

对于事件 2，保证：$1 \le \mathit{id} \le k$ 且编号为 $\mathit{id}$ 的员工在此事件发生时仍在工作。

\begin{array}{|c|c|c|c|c|c|} \hline \textbf{测试点编号} & \mathit{sid} & n \le & k \le & m \le & \textbf{特殊性质} \\ \hline 1 & 1 & 6 & 6 & 6 & \textbf{无} \\ \hline 2, 3 & 2 & 9 & 6 & 6 & \textbf{无} \\ \hline 4, 5 & 3 & 16 & 66 & 66 & \textbf{无} \\ \hline 6 \sim 8 & 4 & 66 & 66 & 0 & \textbf{无} \\ \hline 9 \sim 11 & 5 & 2,333 & 2,333 & 0 & \textbf{无} \\ \hline 12 \sim 14 & 6 & 10^5 & 10^5 & 0 & B \\ \hline 15 \sim 18 & 7 & 10^5 & 10^5 & 0 & \textbf{无} \\ \hline 19 \sim 21 & 8 & 2,333 & 2,333 & 2,333 & A \\ \hline 22 \sim 24 & 9 & 10^5 & 10^5 & 10^5 & AB \\ \hline 25 \sim 28 & 10 & 10^5 & 10^5 & 10^5 & A \\ \hline 29 \sim 31 & 11 & 2,333 & 2,333 & 2,333 & \textbf{无} \\ \hline 32 \sim 34 & 12 & 10^5 & 10^5 & 10^5 & C \\ \hline 35 \sim 38 & 13 & 10^5 & 10^5 & 10^5 & B \\ \hline 39 \sim 44 & 14 & 66,666 & 66,666 & 66,666 & \textbf{无} \\ \hline 45 \sim 50 & 15 & 10^5 & 10^5 & 10^5 & \textbf{无} \\ \hline \end{array}

特殊性质 A：无事件 2；

特殊性质 B：$p_i = i - 1$；

特殊性质 C：$v_i = v = 1$。