Heuristic Merging on Trees

You are given a tree with n nodes numbered from 1 to n (the root is node 1) and each node i has an initial weight v_i. In this problem a heuristic merging is defined as follows.

Initially, every node forms a singleton set with key equal to its weight. A merge operation between two sets A and B is defined using the following rules:

• The key of a set is the sum of the weights of the nodes in that set, denoted by \( S = \sum_{i \in A} v_i \).
• If \( S_A \) and \( S_B \) are different, the set with the smaller sum is merged into the set with the larger sum.
• If \( S_A = S_B \), then the set whose minimum depth is larger (i.e. its smallest depth among all its nodes) is merged into the one with the smaller minimum depth. (All formulas are in \( \LaTeX \) format.)

The merging is done recursively in a bottom–up manner. For a given subtree rooted at x, assume that all child subtrees have been merged into one set each. Then, starting from the subtree root x, the sets are merged with the following enumeration order:

1. Sort the children of a node by their node number in increasing order.
2. Merging is done pair–wise in that order: first merge the set of the root with the first child’s set, then merge the resulting set with the second child’s set, and so on.

After all merges within the subtree have been processed, exactly one set remains. A node is said to have not been merged into another set if it is the representative (i.e. the final surviving set) of its subtree merge.

You are required to process q operations. There are two types of operations:

• 1 x: Query the subtree of node x. After performing the heuristic merging on the whole subtree (i.e. merging the nodes in the manner described above), report the final set's key (i.e. the sum of weights of nodes in that subtree). That is, output \( \sum_{i \in T_x} v_i \), where \( T_x \) is the set of nodes in the subtree of x.
• 2 x d: Increase the weight of node x by d (i.e. perform \( v_x := v_x + d \)).

Note: Although the problem statement describes a sophisticated merging process, the key value of the final merged set in any subtree is simply the sum of the weights of all nodes in that subtree. Thus, your task reduces to performing updates on node weights and answering subtree sum queries on a tree.

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 10⁵), the number of nodes and the number of operations.

The second line contains n integers: v₁, v₂, ..., v_n (\( 0 \le v_i \le 10^9 \)), denoting the initial weight of each node.

The third line contains n-1 integers: p₂, p₃, ..., p_n (1 ≤ p_i ≤ n), where p_i is the parent of node i in the tree. It is guaranteed that the tree is rooted at node 1.

Each of the next q lines represents an operation in one of the following two formats:

• 1 x
• 2 x d

For an operation of type 1, output the subtree sum for node x after merging. For an operation of type 2, update the weight of node x by adding d.

outputFormat

For each query of type 1 x, output a single line containing one integer — the sum of the weights of nodes in the subtree rooted at x (after the corresponding updates), which is also the key of the final merged set.

sample

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

// Explanation:
// Tree with 3 nodes, parent info: node 2 and node 3 have parent 1.
// Query 1 1: sum of subtree rooted at 1 = 1+2+3 = 6
// Query 1 2: subtree rooted at 2 = 2
// Query 2 2 3: update node 2 -> 2+3 = 5
// Query 1 1: now sum = 1+5+3 = 9

6
2
9

</p>