$N$ 個の頂点からなる木（無向サイクルのない連結グラフ）がある。頂点には $1$ から $N$ までの番号が，辺には $1$ から $N-1$ までの番号が付けられている。各頂点には重みがある。

以下の 2 種類のクエリを実行するプログラムを作成せよ。

• 1 u v : $u$ から $v$ へのパス上における最大部分和（空でもよいため，答えは $0$ 以上である）を求め，出力する。
• 2 u v w : $u$ から $v$ へのパス上にあるすべての頂点の重みを $w$ に変更する。

入力

最初の行に $N$ ($2 \le N \le 100{,000}$) が与えられる。

2 行目には，頂点 $1$ から順に各頂点の重みが与えられる。

3 行目から $N-1$ 行には，$i$ 番目の辺が結ぶ 2 つの頂点番号 $u$ と $v$ が与えられる。

次の行にはクエリの個数 $M$ ($1 \le M \le 100{,000}$) が与えられる。

続く $M$ 行には，クエリが 1 行に 1 つずつ与えられる。

頂点の重みは絶対値が $10{,}000$ 以下の整数である。

出力

各クエリの結果を順に 1 行ずつ出力する。

入出力例

入力例 1

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

出力例 1

5
9