011 - 農地開発

問題

イヅア国では国内にある広大な土地を利用して、複数の農園を開拓することになった。

イヅア国ではすでに$N$箇所の農園が開拓されており、農園には$1$から$N$までの番号がついている。農園の間にはそれらを直接つなぐ道が、全部で$N-1$本ある。どの道も同じ長さで、どちらの方向にも通ることができる。また、どの農園からでも、いくつかの道を通っていくことで他のどの農園にも到達できる。また、それぞれの農園では、その農園の収支を記録している。

あなたは新しい任務としてイヅア国の農園の拡張と管理を任される予定である。上司から、以下の２種類の作業をいくつか組み合わせた指示を受け取ることになった。

作業１：農園を新たに開拓し、すでにある農園との間に道を作り接続する。新たに作る道の長さはすでにある道の長さと同じとする。

作業２：農園を２つ指定し、それらの農園をつなぐ最短の経路を見つける。その経路上にある農園の中から、$k$番目に収支の少ない農園の収支を報告する。

あなたは任務が始まる前に、報告すべき収支を計算するプログラムを作っておこうと考えている。

現在の農園の情報と、それぞれの作業に関する情報が与えられたとき、報告すべき農園の収支を出力するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $M$
$b_1$
$b_2$
:
$b_N$
$s_1$ $t_1$
$s_2$ $t_2$
:
$s_{N-1}$ $t_{N-1}$
$op_1$
$op_2$
:
$op_M$

１行目に、すでにある農園の数$N$($2 \leq N \leq 100,000$)と作業の数$M$($1 \leq M \leq 100,000$)が与えられる。続く$N$行に、$i$番目の農園の収支$b_i$($-1,000,000 \leq b_i \leq 1,000,000$)が整数で与えられる。$N-1$行に、２つの農園を直接つなぐ道の情報が与えられる。$s_i$と$t_i$($1\leq s_i$＜$t_i \leq N$)は、$i$番目の道がつなぐ２つの農園の番号である。ただし、どの２つの農園についても、それらを直接つなぐ道は１本以下とする。続く$M$行に、作業を示す情報$op_i$が与えられる。各$op_i$は以下のいずれかの形式で与えられる。

$1$ $u$ $w$

または

$2$ $u$ $v$ $k$

以下では、作業を実行する前の農園の数を$P$とする。最初の文字が$1$の場合、番号が$P+1$となる農園を新たに作り、農園$u$($1 \leq u \leq P$)との間に道を作り接続する作業を示す。その収支は$w$($-1,000,000 \leq w \leq 1,000,000$)である。

最初の文字が2の場合、農園$u$($1 \leq u \leq P$)と農園$v$($1\leq v \leq P$)を最短の道のりでたどったときに訪れるすべての農園の収支のうち、少ないほうから$k$($1 \leq k \leq P$)番目の収支を報告する作業を示す。ただし$k$はこの指示で訪れる農園の数を超えない。

出力

収支を報告する作業ごとに、農園の収支を出力する。

入出力例

入力例

5 9
1
3
1
1
4
1 2
2 3
2 4
4 5
2 2 5 2
1 2 2
2 5 6 2
2 5 6 3
2 5 6 1
1 6 5
1 6 7
2 1 8 3
2 1 8 4

出力例

3
2
3
1
3
7