$N$ 個の頂点からなる根付き木がある。頂点には $1$ から $N$ までの番号が付けられている。頂点 $i$ は重み $A_i$ を持つ。初期状態では、頂点 $r$ が根である。

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

• 0 x y: x の部分木に含まれる頂点の重みを y に変更する。
• 1 r: 木の根を r に変更する。
• 2 x y z: x と y を結ぶパス上の頂点の重みを z に変更する。
• 3 x: x の部分木に含まれる頂点の重みの最小値を出力する。
• 4 x: x の部分木に含まれる頂点の重みの最大値を出力する。
• 5 x y: x の部分木に含まれる頂点の重みに y を加算する。
• 6 x y z: x と y を結ぶパス上の頂点の重みに z を加算する。
• 7 x y: x と y を結ぶパス上の頂点の重みの最小値を出力する。
• 8 x y: x と y を結ぶパス上の頂点の重みの最大値を出力する。
• 9 x y: x の親を y に変更する。ただし、x の部分木の中に頂点 y が存在する場合は、このクエリを無視する。
• 10 x y: x と y を結ぶパス上の頂点の重みの総和を出力する。
• 11 x: x の部分木に含まれる頂点の重みの総和を出力する。

入力

最初の行に二つの整数 $N$, $M$ が与えられる。($1 \le N, M \le 10^5$)

その後 $N-1$ 行には、各辺が結ぶ二つの頂点番号 $u, v$ が与えられる。($1 \le u, v \le N$)

その後 $N$ 行には、頂点 $i$ の重み $A_i$ が与えられる。

その後、初期の根の頂点番号 $r$ が与えられる。($1 \le r \le N$)

その後 $M$ 行には、上記で説明したクエリが与えられる。

入力に現れるすべての整数は C++ の int 型で表現可能であり、クエリを処理する間、すべての頂点の重みの合計が int の範囲を超えないように入力が与えられる。

出力

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

入出力例

入力 1

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

出力 1

9
1
1

入力 2

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

出力 2

173
860
103
791
608
1557