Subtree Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

You are given a tree rooted at vertex 1. Each vertex has a value. Process two types of operations: assign a new value to one vertex, and query the sum of values in the entire subtree of a vertex.

Input

The first line contains $n$ and $q$. The second line contains the $n$ initial vertex 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 of values in the subtree rooted at $s$.

Output

For each operation of type 2, print the requested subtree 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 5
840
1 1 671
2 1
2 1
1 1 331
2 1

Output

671
671
331

Explanation

The only vertex is vertex 1, so each type-2 query returns its current value after all preceding assignments.