Tree Query Operations

You are given a tree with \(n\) nodes numbered from \(1\) to \(n\). Each node has an associated weight \(w_i\). The tree structure is given by \(n-1\) edges connecting the nodes.

You are required to perform \(m\) operations on the tree. There are three types of operations:

• CHANGE u t: Change the weight of node \(u\) to \(t\).
• QMAX u v: Query the maximum weight among all nodes on the unique path from node \(u\) to node \(v\) (inclusive).
• QSUM u v: Query the sum of weights of all nodes on the unique path from node \(u\) to node \(v\) (inclusive).

Note: The path between \(u\) and \(v\) includes both endpoints \(u\) and \(v\).

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of nodes and the number of operations.

The second line contains \(n\) integers: \(w_1, w_2, \ldots, w_n\) indicating the initial weights of the nodes.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) denoting an edge between nodes \(u\) and \(v\).

Then, \(m\) lines follow, each line being one of the three operations in the format described above.

outputFormat

For each query operation (QMAX or QSUM), output the result on a separate line in the order that the queries appear in the input.

sample

3 5
1 2 3
1 2
1 3
QSUM 2 3
QMAX 2 3
CHANGE 1 10
QSUM 2 3
QMAX 2 3

6
3
15
10