Path Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

You are given a tree rooted at vertex 1. Each vertex has a value. Process point assignments and queries asking for the sum of values on the path from the root to a given vertex.

Input

The first line contains $n$ and $q$. The second line contains the $n$ initial values. The next $n-1$ lines contain the tree edges. Each of the following $q$ lines is one of:

• 1 s x: set the value of vertex $s$ to $x$.
• 2 s: query the sum on the path from vertex 1 to vertex $s$.

Output

For each operation of type 2, print the requested path sum.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$.
• $1\le v_i,x\le10^9$.

Example

Input

1 9
544
2 1
2 1
1 1 324
1 1 888
2 1
1 1 672
2 1
1 1 6
2 1

Output

544
544
888
672
6

Explanation

Because the tree contains only vertex 1, every path query returns the current value stored at that vertex.