You are given a one-indexed tree of $N$ nodes and $N-1$ edges. Each node has a weight $w_i$.

Your friend asks you $Q$ questions with regards to the structure of the tree of the following forms:

• 1 r k If the root of the tree is node $r$, what is the heaviness of the $k^{\text{th}}$ heaviest subtree in the tree, where the heaviness of a subtree is the sum of all the weights in that subtree?
• 2 r k If the root of the tree is node $r$, what is the heaviness of the $k^{\text{th}}$ heaviest subtree in the tree, where the heaviness of a subtree is the maximum of all the weights in that subtree?

It is guaranteed that $1\le r,k\le N$. Recall that there are always exactly $N$ subtrees in a tree. The $k^{\text{th}}$ heaviest subtree is out of all the subtrees, not just ones rooted at the children of the root.

Can you answer these questions for your friend?

Input Specification

The first line will contain two integers $N,Q$ $(1\le N,Q\le {10}^5)$.

The next line will contain $N$ integers, $w_i$ $(|w_i|\le {10}^9)$.

The next $N-1$ lines will each contain two integers, $u_i,v_i$ $(1\le u_i,v_i\le N)$, indicating that nodes $u_i$ and $v_i$ are connected by an edge. It is guaranteed that the entire tree is connected.

The next $Q$ lines will each contain a question as defined above.

Output Specification

For each question, output the heaviness of the $k^{\text{th}}$ heaviest subtree if the root of the tree is node $r$, where the definition of heaviness is dependent on the query form.

Subtasks

Subtask 1 [14%]

$N\le 2000$

Subtask 2 [39%]

There will only be type 1 queries.

Subtask 3 [47%]

No additional constraints.

Sample Input for Subtask 1

7 5
5 3 -2 4 -1 0 -2
1 2
1 3
2 7
3 4
3 5
5 6
1 1 3
2 1 3
1 4 5
2 5 7
2 7 4

Sample Output for Subtask 1

1
4
0
-2
4

Sample Input for Subtask 2

6 4
-2 -1 5 -3 2 4
1 2
1 3
3 4
4 5
4 6
1 4 5
1 4 1
1 6 2
1 6 6

Sample Output for Subtask 2

-1
5
2
-3

Sample Input for Subtask 3

20 10
13 17 -7 -14 -5 11 -10 3 -4 8 -17 3 5 5 1 6 5 -9 0 -19
2 1
3 2
4 3
5 3
6 2
7 2
8 7
9 6
10 2
11 1
12 2
13 4
14 6
15 1
16 13
17 8
18 11
19 13
20 10
2 13 3
2 13 6
2 1 18
1 16 9
1 11 10
2 1 2
2 6 15
2 12 15
1 5 8
2 4 4

Sample Output for Subtask 3

17
11
-9
-2
1
17
0
0
3
13