#2020. 「PTS 2023」人员调度

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

该公司初始时有 名优秀员工，编号依次为 。第 名优秀员工初始时在第 个部门工作，并且其有一个能力值 。

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

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

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

：先令 ，然后新增一位编号为 、初始部门为 、能力值为 的优秀员工； ：编号为 的优秀员工将被辞退。

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

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

从文件 transfer.in 中读入数据。

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

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

输入的第三行包含 个正整数 ，表示每个部门的上级部门。

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

接下来 行，每行形如 或 表示一次事件。

输出到文件 transfer.out 中。

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

样例 1 输入

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

样例 1 输出

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。

对于所有的数据，保证：；；；；；；

特殊性质 A：无事件 ；

特殊性质 B：；

特殊性质 C：；