You are given a tree where each edge has a weight of $1$ and each node has a weight.

You need to support two types of operations:

• 1 x y z: Add $z$ to the weights of all nodes on the simple path between $x$ and $y$.
• 2 x y: Query the $y$-th smallest weight among all nodes whose distance to node $x$ is less than or equal to $1$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers representing the initial weights of the nodes.

The next $n-1$ lines each contain two integers $x$ and $y$, representing an edge between $x$ and $y$.

The following $m$ lines each contain an operation in the format 1 x y z or 2 x y, as described above.

Output

For each type 2 operation, output one integer per line representing the answer.

It is guaranteed that an answer exists for every query.

Examples

Input 1

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

Output 1

4
3
4

Note

Idea: nzhtl1477

Solution: nzhtl1477 ($O( n\log^2n/ \log\log n )$ solution), negiizhao ($O( n\log n\log\log\log n )$ solution), ccz181078 ($O( n\log n )$ solution)

Code: nzhtl1477 ($O( n\log^2 n/ \log\log n )$ code)

Data: nzhtl1477 (partially uploaded)

• Subtask 1: $20\%$, $n,m\leq 1000$.
• Subtask 2: $10\%$, the tree is a chain.
• Subtask 3: $20\%$, $n,m\leq 10^5$.
• Subtask 4: $30\%$, $n,m\leq 4\times 10^5$.
• Subtask 5: $20\%$, $n,m\leq 10^6$.

For $100\%$ of the data, $1\leq n,m\leq 10^6$, $0\leq$ value added in each operation $\leq 2000$, $0\leq$ initial node weights $\leq 2000$.