As is well known, the $n$ departments of a company can be organized into a tree structure. Formally, assuming these departments are numbered $1, \dots, n$, then for every department $i \in [2, n]$ except for department 1, there is exactly one superior department $p_i \in [1, i - 1]$. Thus, the $n$ departments of this company can be viewed as a tree rooted at 1. If $i$ is a node in the subtree of $j$, then department $i$ is called a sub-department of department $j$.

Initially, the company has $k$ excellent employees, numbered $1 \dots k$. The $i$-th excellent employee initially works in department $x_i$ and has an ability value $v_i > 0$.

To maximize the company's operational efficiency, the boss $0/\backslash\text{G}$ decides to perform some personnel transfers. Specifically, an excellent employee numbered $i$ can be transferred to a sub-department of $x_i$, or not transferred at all (in which case the employee remains in department $x_i$). Subsequently, the excellent employees in each department will compete for the position of department leader—the one with the highest ability value will hold this position and contribute an amount equal to their ability value to the company. If a department has no excellent employees, no department leader can be selected, and the contribution to the company will be 0. The company's performance is defined as the sum of the contributions of all departments.

The boss $0/\backslash\text{G}$ naturally wants to know how to perform the personnel transfers to maximize the company's performance.

This is certainly not difficult for him; however, the number of excellent employees in the company will also change. Specifically, $m$ events will occur sequentially, each of the following forms:

1 $x$ $v$: First, let $k = k + 1$, then add a new excellent employee numbered $k$ with initial department $x$ and ability value $v$;

2 $id$: The excellent employee numbered $id$ will be dismissed.

The boss $0/\backslash\text{G}$ wants you to tell him the maximum possible performance of the company at the very beginning and after each event.

Note that each personnel transfer is independent, meaning that every time the maximum possible performance of the company is calculated, each excellent employee returns to their initial department.

Input

The input is read from the file transfer.in.

The first line contains a positive integer $sid$, representing the data range and special properties of the test case.

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

The third line contains $n - 1$ positive integers $p_2, \dots, p_n$, representing the superior department of each department.

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

The next $m$ lines each contain an event of the form 1 x v or 2 id.

Output

The output is written to the file transfer.out.

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

Examples

Input 1

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

Output 1

4 5

Data Range

For all data, it is guaranteed that: $1 \le 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 id \le k$ and the employee with number $id$ is still working when this event occurs.

Special Property A: No event 2.

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

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