Il y a un arbre (graphe connexe sans cycle non orienté) composé de $N$ sommets. Les sommets sont numérotés de $1$ à $N$, et les arêtes sont numérotées de $1$ à $N-1$. La couleur d’un sommet est noire ou blanche et chaque sommet possède un poids.

Écrivez un programme qui exécute les trois types de requêtes suivants :

• 1 i : Changer la couleur du i‑ième sommet (blanc $\to$ noir, noir $\to$ blanc).
• 2 u : Trouver et afficher le sommet $v$ connecté à $u$ ayant le plus grand poids. Deux sommets sont connectés si tous les sommets sur le chemin les reliant sont de la même couleur. Ici, $u$ et $v$ peuvent être identiques.
• 3 u w : Changer le poids du u‑ième sommet en $w$.

Entrée

La première ligne contient $N$ ($2 \le N \le 100\,000$).

Les $N-1$ lignes suivantes contiennent deux entiers $u$ et $v$ (les deux sommets reliés par la i‑ième arête).

La ligne suivante contient les couleurs des sommets $1$ à $N$ : un entier $0$ (noir) ou $1$ (blanc).

La ligne suivante contient les poids des sommets $1$ à $N$, dans l’ordre.

La ligne suivante contient le nombre de requêtes $M$ ($1 \le M \le 100\,000$).

Les $M$ lignes suivantes décrivent une requête par ligne.

Tous les poids sont des entiers naturels inférieurs ou égaux à $10^9$.

Sortie

Afficher le résultat de chaque requête de type $2$, dans l’ordre, un par ligne.

Exemples

Entrée 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

Sortie 1

1
5

Entrée 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

Sortie 2

7
5
7