Migrated from Lutece 2847 The Journey of Elaina

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

One day, Elaina travels to The Kingdom of River, which consists of $N$ cities and they are connected by $N-1$ tributaries.

The capital of The Kingdom of River is City $1$ located on the estuary and all the streamflow was finally converged here.

If the tributary of City $X$ passes through City $Y$ and reaches the estuary, $X$ is said to be downstream of $Y$.

Now, there is streamflow for every city, which can be changed over time. The king wonders what is the sum of the streamflow for City $C$ and all its downstream cities. As the youngest, most beautiful, and most intelligent witch, Elaina, will solve this problem as easily as blowing off dust.

Input

The first line contains one integer $N\ (2 \le N \le 10^5)$ indicating the number of cities.

The second line contains $N$ integers, indicating the array $F_i\ (1 \le F_i \le 10^4)$. The $i$-th integer indicates the streamflow for City $i$.

The third line contains $N-1$ integers, indicating the array $P_i\ (1 \le P_i \le i)$. The $i$-th integer indicates that there is a tributary between $i+1$ and $P_i$.

The next line contains one integer $Q\ (1 \le Q \le 10^5)$ indicating the number of operations.

For the next $Q$ lines, the first integer $\text{op}$ indicates the type of operation.

• If $\text{op}=1$, following two integers $c, w\ (1\le c \le N, 1 \le w \le 10^4)$ indicate the streamflow for City $c$ changing to $w$.
• If $\text{op}=2$, following one integer $c\ (1\le c \le N)$ indicates the king's query for the sum of the streamflow for City $c$ and all its downstream cities.

Output

For every query, i.e. $\text{op}=2$ operation, output one line with an integer as the answer.

Samples

3
1 2 3
1 1
4
2 1
2 3
1 1 2
2 1

6
3
7

Resources

The 18th UESTC Programming Contest Preliminary