Tree Queries

Given a tree with n nodes, where each node has an initial value, you are to process a series of queries. The tree is rooted at node 1. There are two types of queries:

• 1 u: Query the sum of all node values in the subtree rooted at node \(u\). The subtree of \(u\) includes \(u\) itself and all of its descendants.
• 2 u x: Update the value of node \(u\) to \(x\).

You are required to process the queries and output the result for each type \(1\) query in the order they occur. Use the following input and output format.

Note: The queries and updates are processed sequentially. When answering a query of type 1, the update queries prior to it have already affected the tree.

Recall that the subtree sum for node \(u\) is computed as:

\[ S(u)=\sum_{v\in \text{subtree}(u)}value(v) \]

inputFormat

The first line contains two integers n and q, denoting the number of nodes and the number of queries respectively.

The second line contains n integers, where the i^th integer represents the initial value of node i.

The next n - 1 lines each contain two integers u and v, representing an edge between node u and node v in the tree.

The following q lines each describe a query, in one of the following formats:

• 1 u for a subtree sum query.
• 2 u x for updating the value of node u to x.

outputFormat

For each query of type 1, output the sum of the subtree rooted at the specified node. Each output should be printed on a separate line, in the order of the queries.

## sample

5 3
1 2 3 4 5
1 2
1 3
3 4
3 5
1 1
2 3 10
1 3

15
19

</p>