Weighted Tree Operations

Given a rooted tree with \( n \) nodes. Each node has an initial weight. You need to process \( q \) operations on the tree. The operations are of the following twelve types:

• 0 x y: Set the weight of every node in the subtree of \( x \) to \( y \).
• 1 x: Change the root of the tree to node \( x \).
• 2 x y z: Set the weight of every node on the simple path from \( x \) to \( y \) to \( z \).
• 3 x: Query the minimum weight in the subtree of \( x \).
• 4 x: Query the maximum weight in the subtree of \( x \).
• 5 x y: Increase the weight of every node in the subtree of \( x \) by \( y \).
• 6 x y z: Add \( z \) to every node on the simple path from \( x \) to \( y \).
• 7 x y: Query the minimum weight on the simple path from \( x \) to \( y \).
• 8 x y: Query the maximum weight on the simple path from \( x \) to \( y \).
• 9 x y: Change the parent of \( x \) to \( y \). (If \( y \) is in the subtree of \( x \), this operation is ignored.)
• 10 x y: Query the sum of weights on the simple path from \( x \) to \( y \).
• 11 x: Query the sum of weights in the subtree of \( x \).

Note: The subtree of a node is defined with respect to the current designated root. All paths are the unique simple paths in the tree.

inputFormat

The first line contains two integers \( n \) and \( q \) (\( 1 \le n, q \le 10^5 \)), representing the number of nodes and the number of operations. The second line contains \( n \) integers, the initial weights of the nodes (indexed from 1). The next \( n-1 \) lines each contain two integers \( u \) and \( v \), indicating there is an edge between nodes \( u \) and \( v \) in the tree. The following \( q \) lines each describe an operation in one of the formats detailed above.

outputFormat

For each query operation (i.e. operations 3, 4, 7, 8, 10, and 11), output the result on a separate line.

sample

5 7
1 2 3 4 5
1 2
1 3
3 4
3 5
3 3
0 3 10
3 3
2 2 4 5
10 2 4
1 3
7 2 4

3
10
20
5