$N$ 個の頂点からなる木 (無向で閉路のない連結グラフ) がある。頂点には $1$ から $N$ までの番号が付けられており、辺には $1$ から $N-1$ までの番号が付けられている。各頂点は黒色または白色であり、重みを持つ。

以下の 3 種類のクエリを処理するプログラムを作成せよ。

• 1 i: 頂点 $i$ の色を反転する。（白色 $\to$ 黒色、黒色 $\to$ 白色）
• 2 u: 頂点 $u$ と連結である頂点 $v$ のうち、重みが最大のものを求め、出力する。二つの頂点が連結であるとは、それらを結ぶ経路上の全ての頂点の色が同じであることを意味する。なお、$u$ と $v$ は同じでもよい。
• 3 u w: 頂点 $u$ の重みを $w$ に変更する。

入力

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

続く $N-1$ 行には、$i$ 番目の辺が結ぶ二つの頂点の番号 $u$ と $v$ が与えられる。

次の行には、頂点 $1$ から頂点 $N$ までの色が与えられる。色は $0$ または $1$ であり、$0$ は黒色、$1$ は白色を表す。その次の行には、各頂点の重みが頂点 $1$ から順に与えられる。

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

続く $M$ 行には、各クエリが一行に一つずつ与えられる。

全ての重みは $10^9$ 以下の自然数である。

出力

各 $2$ 番目のクエリの結果を、順に一行ずつ出力せよ。

入出力例

入力 1

5
1 2
1 3
1 4
1 5
0 1 1 1 1
1 2 3 4 5
3
2 1
1 1
2 1

出力 1

1
5

入力 2

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

出力 2

7
5
7