Emotional Resonance Analysis

You are given a rooted tree with n nodes numbered from 1 to n with node 1 as the root. Each node x has an initial mood M_x = (a_x, a_x). A mood is represented as a 2-tuple \(M=(s, f)\) where both s (the total intensity) and f (the featured emotion) are positive integers.

The resonance operation is defined between two moods \(M_1=(s_1,f_1)\) and \(M_2=(s_2,f_2)\) as follows:

[ M_1 + M_2 = (s_1+s_2, f_1) \quad \text{and} \quad M_2 + M_1 = (s_1+s_2, f_2), ]

Note that the operation is not necessarily commutative.

A heart road in the tree is the following process applied on the subtree rooted at r:

1. Initialize A_r ← M_r.
2. For each child x of node r in increasing order of node number, compute the heart road of the subtree rooted at x resulting in A_x, then update A_r as follows:
   • If \(s_r \geq s_x\), set \(A_r \gets A_r + A_x = (s_r+s_x, f_r)\).
   • Otherwise, set \(A_r \gets A_x + A_r = (s_r+s_x, f_x)\).

Your task is to process q operations. Each operation is one of the following types:

1. Query: Given a node x, recalculate the heart road for the subtree rooted at x based on the current values and output the featured emotion f of the final mood \(A_x=(s_x,f_x)\).
2. Update: Given a node x and an integer d (which may be negative), update a_x ← a_x + d, and accordingly update M_x. It is guaranteed that before and after every update, a_x > 0.

Note: In each query, the heart road is recalculated from scratch using the current values.

inputFormat

The input begins with two integers n and q (1 ≤ n, q ≤ some limit) representing the number of nodes and the number of operations.

The second line contains n positive integers \(a_1, a_2, \ldots, a_n\) where \(a_x\) is the initial value for node x.

Each of the next n - 1 lines contains two integers u and v indicating that node u is the parent of node v in the tree.

The following q lines each describe an operation. An operation is in one of the following two formats:

• 1 x — Query the featured emotion at subtree rooted at x.
• 2 x d — Update node x by adding d to its current value (\(d\) may be negative, but the updated value remains positive).

outputFormat

For each query operation (type 1), output a single line containing the featured emotion f of the final mood \(A_x=(s_x,f_x)\) for the queried node.

sample

3 3
5 3 2
1 2
1 3
1 1
2 2 -1
1 1

5
5

</p>