Subtree Maximum Query and Simultaneous Update

You are given a rooted tree with n nodes, rooted at node 1. Each node i has an initial weight a_i. The tree supports two types of operations:

1. 1 u: Query the maximum weight in the subtree of node u.
2. 2 u: Update every node x in the subtree of u simultaneously by setting \[ a_x \gets \sum_{y \in \operatorname{son}(x)} a_y, \] where \(\operatorname{son}(x)\) denotes the set of immediate children of node \(x\). (Note: For a leaf, since it has no children, its new weight becomes 0.)

Note: In the update operation, the new weights are computed based on the old weights of the children before any of them are updated (i.e. the update is simultaneous).

inputFormat

The first line contains two integers n and Q — the number of nodes and the number of operations.

The second line contains n integers: a1, a2, ..., an representing the initial weight of each node.

Each of the next n − 1 lines contains two integers u and v, indicating that there is an edge between nodes u and v. It is guaranteed that these edges form a tree with root 1.

The following Q lines each contain an operation in one of the following forms:

1 u
2 u

outputFormat

For each operation of the first type (i.e. queries), output a line containing the maximum weight found in the subtree of the given node.

sample

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

5
9
12