G. Crown
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$k$$$ cows playing a game, each positioned on distinct nodes of a tree of size $$$n$$$ rooted at node $$$1$$$. The $$$i$$$-$$$th$$$ cow has been assigned a value, $$$val_i$$$. Every node can be either blocked or not blocked. Initially, no node is blocked. In each second of the game, every cow chooses to make one of the following moves:

  • Stay at its current node, or
  • If it is at node $$$u$$$ and $$$p_u$$$ has not been blocked, move to $$$p_u$$$, where $$$p_u$$$ is the parent of node $$$u$$$.

If in a second every cow chooses to stay at its current node, the game ends. The last second does not count towards the total amount of seconds the game lasted. Multiple cows may be on the same node by the end of a game. The sum of a node is the sum of the values of the cows on that node when the game ends. The score of the game is the sum of the node with the maximal sum among all other nodes. After a game ends, all cows return to their starting nodes. The goal of the cows is to maximize the score of the game in as little time as possible.

However, SpyrosAliv does not like cows; therefore, he will try to ruin their game.

Specifically, there will be $$$q+1$$$ games. The first game will be played without any changes. Before the $$$i$$$-$$$th$$$ of the next $$$q$$$ games starts, SpyrosAliv will do one of the following:

  1. remove the cow from node $$$u_i$$$, or
  2. block node $$$u_i$$$ (there is no cow on that node)

Note that changes done on game $$$j$$$ are not reverted and affect all following games $$$j, j+1, ..., q, q+1$$$.

For each game, help Cow the Cow calculate the score of the game and how long it lasted if the cows played optimally.

Input

The first line of the input contains two integers, $$$n$$$ and $$$k$$$, $$$(1 \le k \le n \le 2 \cdot 10^5)$$$.

The second line of the input contains $$$k$$$ distinct integers, where the $$$i$$$-$$$th$$$ integer is the position of the $$$i$$$-$$$th$$$ cow.

The third line of the input contains $$$k$$$ integers, $$$val_1, val_2, ..., val_k$$$ $$$(1 \le val_i \le 10^9)$$$, the value of the $$$i$$$-$$$th$$$ cow.

The fourth line of the input contains $$$n-1$$$ integers $$$p_2, p_3, ..., p_n$$$, where $$$p_i$$$ $$$(1 \le p_i \le n)$$$ is the parent of the $$$i$$$-$$$th$$$ node.

The following line contains exactly one integer, $$$q$$$ $$$(0 \le q \le n)$$$, the number of queries.

The $$$i$$$-$$$th$$$ of the next $$$q$$$ lines contains two integers, $$$t_i$$$ and $$$u_i$$$ $$$(1 \le t_i \le 2, 1 \le u_i \le n)$$$, the type of the $$$i$$$-$$$th$$$ query and its node respectively. If $$$t_i = 1$$$, then SpyrosAliv removes the cow from node $$$u_i$$$. If $$$t_i = 2$$$, then SpyrosAliv blocks node $$$u_i$$$.

It is guaranteed that if $$$t_i = 1$$$, there is a cow at node $$$u_i$$$. If $$$t_i = 2$$$, $$$u_i$$$ is not blocked and has no cow.

It is guaranteed that the input provides a valid tree.

Output

Output $$$q + 1$$$ lines.

On the $$$i$$$-$$$th$$$ line, output two integers: the score of the $$$i$$$-$$$th$$$ game and the seconds it lasted if the cows played optimally.

Examples
Input
7 4
2 3 5 7
5 3 8 2
1 2 2 4 4 4
7
1 2
2 2
2 4
1 5
1 3
1 7
2 5
Output
18 2
13 2
10 1
8 0
3 0
2 0
0 0
0 0
Input
5 4
3 4 5 2
1 10 5 7
5 2 2 1
5
2 1
1 4
1 3
2 3
2 4
Output
23 2
23 2
13 2
12 1
12 1
12 1
Input
5 3
5 2 4
1891 54 5645
5 1 1 4
5
2 3
1 4
1 5
2 5
1 2
Output
7590 2
7590 2
1945 1
54 0
54 0
0 0
Note

On the first example, this is what the tree looks like before the third game:

Green nodes have a cow on them, and their label is the value of their cow. Node $$$2$$$ has been blocked. The optimal moves for the cows are the following:

  • At second $$$1$$$, cows at nodes $$$5$$$ and $$$7$$$ will move upwards to node $$$4$$$. Note that the cow at node $$$3$$$ can not make a move, since its parent has been blocked.
  • At second $$$2$$$, no cow can make a move. The game ends since no cow made a move. This second does not count towards the total seconds the game lasted.

The game has lasted $$$1$$$ second. Node $$$4$$$ has a sum of $$$10$$$, node $$$3$$$ has a sum of $$$3$$$, and all other nodes have a sum of $$$0$$$. The score of the game is the sum of node $$$4$$$, which is $$$10$$$. The cows needed $$$1$$$ second to achieve this score. It can be shown that $$$10$$$ is the maximal possible score they can achieve, and that they need at least $$$1$$$ second to achieve it.

After the game ends, all cows return to their starting nodes. That means that the image above represents the tree both before and right after the third game.