Problem Description

As is well known, the $n$ departments of a company can be organized into a tree structure. Formally, if these departments are numbered sequentially as $1, \ldots, n$, then for each department $i \in [2, n]$, there is exactly one superior department $p_i \in [1, i - 1]$. Thus, the $n$ departments of the company can be viewed as a tree rooted at 1. If $i$ is a node in the subtree of $j$, then department $i$ is considered a subordinate department of $j$.

Initially, the company has $k$ outstanding employees, numbered sequentially from $1$ to $k$. The $i$-th outstanding employee initially works in department $x_i$ and has a capability value $v_i > 0$.

To maximize the operational efficiency of the company, the boss 0/\/\G has decided to make some personnel adjustments. Specifically, the $i$-th outstanding employee can be moved to a subordinate department of $x_i$, or not moved at all (remaining in department $x_i$). Subsequently, the outstanding employees will compete for the position of department head in their respective departments—the one with the highest capability value will be appointed, contributing an amount equal to their capability value to the company. If no outstanding employees are present in a department, no department head can be elected, and the contribution from that department will be $0$. The company's performance is defined as the sum of contributions from all departments.

Naturally, the boss 0/$/\G$ wants to know how to make these adjustments to maximize the company's performance.

This task is not beyond him, however, the number of outstanding employees in the company also changes; specifically, $m$ events will occur sequentially, each of which is either:

• 1 x v: Increase $k$ by 1, then add a new outstanding employee numbered $k$ with an initial department $x$ and capability value $v$;
• 2 id: The outstanding employee numbered $\mathit{id}$ will be dismissed.

The boss 0/$/\G$ hopes you can inform him of the maximum possible performance of the company initially and after each event.

Note that each personnel adjustment is independent, meaning that each time the maximum possible performance is calculated, every outstanding employee returns to their initial department.

Input Format

The first line of input contains a positive integer $\mathit{sid}$, indicating the data range and special properties for this test point, detailed in the table below.

The second line contains three integers $n, k, m$, representing the number of departments, the initial number of outstanding employees, and the number of events, respectively.

The third line contains $n - 1$ positive integers $p_2, \ldots, p_n$, indicating the superior department for each department.

The next $k$ lines each contain two positive integers $x_i, v_i$, representing the initial department and capability value of each outstanding employee.

The following $m$ lines each describe an event, formatted as either 1 x v or 2 id.

Output Format

Output a single line containing $m + 1$ non-negative integers separated by single spaces, sequentially indicating the maximum possible performance of the company initially and after each event.

Sample Input and Output

Input Sample #1

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

Output Sample #1

4 5

Input Sample #2

See attached file transfer/transfer2.in

Output Sample #2

See attached file transfer/transfer2.ans

Input Sample #3

See attached file transfer/transfer3.in

Output Sample #3

See attached file transfer/transfer3.ans

Input Sample #4

See attached file transfer/transfer4.in

Output Sample #4

See attached file transfer/transfer4.ans

Input Sample #5

See attached file transfer/transfer5.in

Output Sample #5

See attached file transfer/transfer5.ans

Input Sample #6

See attached file transfer/transfer6.in

Output Sample #6

See attached file transfer/transfer6.ans

Input Sample #7

See attached file transfer/transfer7.in

Output Sample #7

See attached file transfer/transfer7.ans

Input Sample #8

See attached file transfer/transfer8.in

Output Sample #8

See attached file transfer/transfer8.ans

Input Sample #9

See attached file transfer/transfer9.in

Output Sample #9

See attached file transfer/transfer9.ans

Input Sample #10

See attached file transfer/transfer10.in

Output Sample #10

See attached file transfer/transfer10.ans

Input Sample #11

See attached file transfer/transfer11.in

Output Sample #11

See attached file transfer/transfer11.ans

Input Sample #12

See attached file transfer/transfer12.in

Output Sample #12

See attached file transfer/transfer12.ans

Input Sample #13

See attached file transfer/transfer13.in

Output Sample #13

See attached file transfer/transfer13.ans

Input Sample #14

See attached file transfer/transfer14.in

Output Sample #14

See attached file transfer/transfer14.ans

Input Sample #15

See attached file transfer/transfer15.in

Output Sample #15

See attached file transfer/transfer15.ans

Notes/Hints

[Data Range]

For all data, it is guaranteed that: $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$.

For event 2, it is guaranteed that: $1 \le \mathit{id} \le k$ and the employee numbered $\mathit{id}$ is still employed at the time of this event.

Special Property A: No event 2;

Special Property B: $p_i = i - 1$;

Special Property C: $v_i = v = 1$.

见题面 Input 部分

见题面 Output 部分