Tree Path Update and Neighbor Query

You are given a tree with node weights and all edges having weight \(1\). You need to process two types of operations on the tree:

• 1 x y z: Add \(z\) to the weight of each node on the simple (unique) path from node \(x\) to node \(y\).
• 2 x y: Query the \(y\)th smallest weight among all nodes whose distance from node \(x\) is at most \(1\) (i.e. node \(x\) and all its immediate neighbors).

Note: It is guaranteed that every query is valid, i.e. the value \(y\) is between \(1\) and the number of nodes in the queried set.

inputFormat

The input begins with two integers \(n\) and \(m\) where \(n\) is the number of nodes and \(m\) is the number of operations. The nodes are numbered from \(1\) to \(n\).

The second line contains \(n\) integers, the initial weights of the nodes.

Then follow \(n-1\) lines, each containing two integers \(u\) and \(v\) indicating there is an edge between nodes \(u\) and \(v\) (all edges have weight \(1\)).

Finally, there are \(m\) lines, each representing an operation in one of the following formats:

• 1 x y z — update: add \(z\) to each node weight on the simple path from \(x\) to \(y\).
• 2 x y — query: among the set of nodes that are at distance at most \(1\) from node \(x\), output the \(y\)th smallest weight.

outputFormat

For each query operation (type 2), output the answer on a separate line.

sample

5 5
5 3 7 1 9
1 2
1 3
3 4
3 5
2 3 2
1 2 4 10
2 3 2
2 5 1
2 1 2

5
11
9
15