Mamy drzewo (spójny graf nieskierowany bez cykli) składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Każdy wierzchołek ma kolor (czarny lub biały) oraz wagę.

Napisz program, który obsługuje trzy rodzaje zapytań:

• 1 i: Zmień kolor wierzchołka $i$ (biały $\to$ czarny, czarny $\to$ biały).
• 2 u: Znajdź i wypisz wagę wierzchołka $v$ połączonego z $u$ o największej wadze. Dwa wierzchołki są połączone, jeśli wszystkie wierzchołki na ścieżce między nimi mają ten sam kolor. $u$ i $v$ mogą być tym samym wierzchołkiem.
• 3 u w: Zmień wagę wierzchołka $u$ na $w$.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \le N \le 100\,000$).

Kolejne $N-1$ wierszy zawiera po dwie liczby $u$ i $v$ oznaczające krawędź $i$.

Następny wiersz zawiera $N$ liczb – kolory wierzchołków od $1$ do $N$. $0$ oznacza czarny, $1$ oznacza biały.

Kolejny wiersz zawiera $N$ liczb – wagi wierzchołków w kolejności od $1$ do $N$.

Następny wiersz zawiera $M$ ($1 \le M \le 100\,000$) – liczbę zapytań.

Każdy z kolejnych $M$ wierszy zawiera jedno zapytanie.

Wszystkie wagi są liczbami naturalnymi nie większymi niż $10^9$.

Wyjście

Dla każdego zapytania typu $2$ wypisz wynik w osobnym wierszu, w kolejności występowania.

Przykład

Wejście 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

Wyjście 1

1
5

Wejście 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

Wyjście 2

7
5
7