問題文

$1$ から $N$ の番号がついた $N$ 個の都市からなる都市群と、$1$ から $N-1$ の番号がついた $N-1$ 本の道があります。 道 $i$ は都市 $u_i$ と都市 $v_i$ を繋いでおり、道で繋がれた都市同士は双方向に移動が可能です。 また各都市は都市 $1$ からいくつかの道を経由して到達可能です。

あなたは都市群の交通管理局の局員です。 交通管理局には、各都市の天候の悪さを表す 悪天候度 のデータから都市間の移動の 過酷さ を算出する役割があります。 都市 $v$ の悪天候度は $a_v$ で表され、また都市 $u$-$v$ 間の移動の過酷さは以下で定義されます。

• 都市 $u$ から $v$ への最短経路上の都市の集合（ $u, v$ を含む）を $P$ とする。「 $P$ に属する都市、あるいはそれらのいずれかと $1$ 本の道で直接つながる都市」の悪天候度の総和。

さて、入力として現在時刻における各都市の悪天候度 $a_1 , a_2 , \dots , a_N$ とこれから順に起こる $Q$ 個のイベントの情報が与えられます。 イベントは二種類存在し、それぞれ以下のとおりです。

• 0 v x : 都市 $v$ の悪天候度 $a_v$ が $x$ 増加した。
• 1 u v : 市民から都市 $u$ から都市 $v$ への移動のリクエストがあった。

交通管理局には、市民から都市間の移動をリクエストされるたびにリクエストした市民にその都市間を移動する過酷さを伝える義務があります。
交通管理局の局員として、各 1 u v の形式のイベントに対する「その時点での都市 $u$-$v$ 間の移動の過酷さ」を時系列順に出力してください。

入力

入力は以下の形式で標準入力から与えられます。
ただし、$\mathrm{event}_i$ は $i$ 番目に起こったイベントの形式を表します。

$N \space Q$
$a_1$ $a_2$ $\dots$ $a_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$\mathrm{event}_1$
$\mathrm{event}_2$
$\vdots$
$\mathrm{event}_Q$

出力

各 1 u v の形式のイベントに対する「その時点での都市 $u$-$v$ 間の移動の過酷さ」を、それぞれ一行ずつ時系列順に出力してください。 最後に改行してください。

制約

• 入力はすべて整数
• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $|a_v| \leq 10^9$ ($ 1 \leq v \leq N $)
• $1 \leq u_i , v_i \leq N$ ($1 \leq i \leq N - 1 $)
• $u_i \neq v_i$ ($1 \leq i \leq N - 1 $)
• $\mathrm{event}_i$ は 0 v x または 1 u v の形式で与えられる ($1 \leq i \leq Q$)。
• 0 v x の形式のイベントにおいて、$1 \leq v \leq N$ かつ $|x| \leq 10^9$ を満たす。
• 1 u v の形式のイベントにおいて、$1 \leq u , v \leq N$ かつ $u \neq v$ を満たす。
• 1 u v の形式のイベントが少なくとも $1$ 度与えられる。
• 任意の $2$ 都市間を、与えられた道のみを使って移動することができる。

サンプル

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

6
15
9
10