Given a tree with $n$ nodes, each node has a weight $v_i$.

In this problem, heuristic merging refers to recursively performing bottom-up set merging. In each step, using the sum of weights of the sets as the key, the points in the set with the smaller weight sum are added to the set with the larger weight sum. Initially, each set contains only the node itself.

We define the enumeration order as follows: assume all subtrees have been recursively merged. When merging at the current node, start from the root of the subtree, sort the children by their indices in ascending order, and merge the sets pairwise to obtain the set for the subtree.

Additionally, if two sets have the same weight sum, use the minimum depth of the nodes in the set as the secondary criterion (the set with the larger minimum depth is merged into the set with the smaller minimum depth).

The root of the tree is fixed at $1$. The following query and update operations are provided:

1 x queries the weight of the node that has not been "merged into another set" after performing the heuristic merging on the subtree rooted at $x$.

2 x d adds $d$ to the weight of node $x$.

Input

The first line contains two integers $n$ and $q$, representing the size of the tree and the number of operations, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ is the initial weight of node $i$.

The third line contains $n-1$ integers $p_2, p_3, \dots, p_n$, where $p_i$ is the parent of node $i$ when the tree is rooted at $1$.

The next $q$ lines each contain an operation in the format 1 x or 2 x d, corresponding to the two types of operations described above.

Output

For each operation of type $1$, output a single integer representing the answer.

Examples

Input 1

5 10
2 10 1 10 3
1 2 3 2
2 1 3
1 3
1 5
2 3 5
2 3 2
1 5
2 5 6
1 3
2 5 -1
2 3 0

Output 1

10
3
3
10

Subtasks

Idea: FutaRimeWoawaSete, Solution: zhoukangyang, Code: Rainybunny, Data: FutaRimeWoawaSete/Rainybunny

For $100\%$ of the data, $1 \le n, q \le 2 \times 10^5$, $1 \le p_i < i$; for the operations, $x \in [1, n]$, $d \in [-10^{18}, 10^{18}]$; at any time $a_x \ge 1$ and $\sum_{x=1}^n a_x \le 10^{18}$.