F. Fill the Gym with Argon
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lacking the funds to fill the contest floor with argon, BAPC is looking for ways to raise money!

There are $$$n$$$ fundraising activities that BAPC can hold, conveniently numbered $$$1$$$ through $$$n$$$. Holding the $$$i$$$-th activity earns BAPC a profit of $$$a_i$$$ dollars (this number can be positive, zero, or even negative). Furthermore, each activity $$$2 \leq i \leq n$$$ has a prerequisite $$$r_i$$$  — meaning you cannot hold activity $$$i$$$ without also holding activity $$$r_i$$$.

Of course, BAPC wants to maximize their profits, so they will choose a subset of activities that earns the maximum possible profit. If there are multiple such subsets, they choose a subset with the maximum number of activities (gotta look busy!).

So, the subset of activities that BAPC holds can be described by two integers: the profit made, and the number of activities held. We'll call these the optimal profit, and the optimal number of activities respectively.

But now the fundraising team wants to spice things up a bit by changing some $$$a_i$$$ values. You are given $$$q$$$ queries you need to answer, of two types:

  • Type $$$1$$$: given an integer $$$v_i$$$ and value $$$x_i$$$, increase the profit of activity $$$v_i$$$ by $$$x_i$$$  — in other words, do $$$a_{v_i} := a_{v_i} + x_i$$$. It is guaranteed that $$$x_i$$$ is positive.
  • Type $$$2$$$: given an integer $$$v_i$$$, find the smallest positive integer $$$x_i$$$ such that increasing $$$a_{v_i}$$$ by $$$x_i$$$ will change either the optimal profit made, or the optimal number of activities held.

Type $$$1$$$ updates are persistent, meaning that changes made to $$$a_i$$$ remain in effect for future queries. Type $$$2$$$ updates do NOT change the values of $$$a_i$$$.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \leq t \leq 1.5\cdot 10^5$$$).

The first line of each test contains $$$n$$$  — the number of activities ($$$2 \leq n \leq 3\cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).

The third line contains $$$n-1$$$ integers $$$r_2, r_3, \ldots, r_n$$$, the prerequisites ($$$1 \leq r_i \leq i-1$$$).

The fourth line contains $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$).

The next $$$q$$$ lines describe the queries. Each line starts with either a $$$1$$$ or a $$$2$$$.

  • If the line starts with a $$$1$$$, it is followed by two integers $$$v_i$$$ and $$$x_i$$$ ($$$1 \leq v_i \leq n$$$, $$$1 \leq x_i \leq 10^9$$$).
  • If the line starts with a $$$2$$$, it is followed by one integer $$$v_i$$$ ($$$1 \leq v_i \leq n$$$).

It is guaranteed that the sum of $$$n$$$ across all tests, and the sum of $$$q$$$ across all tests both do not exceed $$$3\cdot 10^5$$$.

Output

For each test, output the answers to each type $$$2$$$ query.

Example
Input
3
4
-2 0 0 0
1 1 2
3
2 3
1 1 10
2 1
4
100 -600 200 300
1 2 2
4
2 2
2 3
1 2 100
2 4
6
52 -42 6 5 -2 -93
1 2 3 2 1
8
1 3 76
1 5 35
2 5
2 6
1 6 94
1 1 20
1 2 25
2 4
Output
2
1
100
100
1
1
93
1
Note

In the first test, the optimal strategy is initially not to hold any events at all. All events depend (directly or indirectly) on event $$$1$$$, which loses $$$2$$$ dollars. But no event makes any money to make up for it.

However, in the first query, if we were to change the profit of $$$a_3$$$ from $$$0$$$ to $$$2$$$, the optimal strategy would be to hold all events. The profit earned would still be $$$0$$$, but we would now be holding $$$4$$$ events, more than the $$$0$$$ events we were holding before. Note that in a type $$$2$$$ query, the change is purely hypothetical, and the values of $$$a$$$ are not actually changed.

In the second query, we change $$$a_1$$$ from $$$-2$$$ into $$$8$$$. The optimal strategy is now to host all events, earning an optimal profit of $$$8$$$ dollars.

In the third query, we just need to change $$$a_1$$$ from $$$8$$$ to $$$9$$$ if we want to change the optimal profit. This is a difference of $$$1$$$, so we output $$$1$$$.