众所周知，一个公司的 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 3 2 1 1 1 2 1 1 3 1 2 2
4 5
对于所有的数据，保证：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} 的员工在此事件发生时仍在工作。
| 测试点编号 | \mathit{sid} | n \le | k \le | m \le | 特殊性质 |
|---|---|---|---|---|---|
| 1 | 1 | 6 | 6 | 6 | 无 |
| 2, 3 | 2 | 9 | 6 | 6 | 无 |
| 4, 5 | 3 | 16 | 66 | 66 | 无 |
| 6 ~ 8 | 4 | 66 | 66 | 0 | 无 |
| 9 ~ 11 | 5 | 2,333 | 2,333 | 0 | 无 |
| 12 ~ 14 | 6 | 10^5 | 10^5 | 0 | B |
| 15 ~ 18 | 7 | 10^5 | 10^5 | 0 | 无 |
| 19 ~ 21 | 8 | 2,333 | 2,333 | 2,333 | A |
| 22 ~ 24 | 9 | 10^5 | 10^5 | 10^5 | AB |
| 25 ~ 28 | 10 | 10^5 | 10^5 | 10^5 | A |
| 29 ~ 31 | 11 | 2,333 | 2,333 | 2,333 | 无 |
| 32 ~ 34 | 12 | 10^5 | 10^5 | 10^5 | C |
| 35 ~ 38 | 13 | 10^5 | 10^5 | 10^5 | B |
| 39 ~ 44 | 14 | 66,666 | 66,666 | 66,666 | 无 |
| 45 ~ 50 | 15 | 10^5 | 10^5 | 10^5 | 无 |
特殊性质 A：无事件 2；
特殊性质 B：p_i = i - 1；
特殊性质 C：v_i = v = 1。
联合省选