Hay un árbol (grafo conexo acíclico no dirigido) con $N$ vértices. Los vértices están numerados del $1$ al $N$, y las aristas están numeradas del $1$ al $N-1$. Cada vértice tiene un color (negro o blanco) y un peso.

Escriba un programa que realice las siguientes tres consultas:

• 1 i: Cambiar el color del vértice $i$ (blanco $\to$ negro, negro $\to$ blanco).
• 2 u: Encontrar e imprimir el vértice $v$ con el peso máximo entre los vértices conectados a $u$. Dos vértices están conectados si todos los vértices en el camino que los une tienen el mismo color. En este caso, $u$ y $v$ pueden ser el mismo.
• 3 u w: Cambiar el peso del vértice $u$ a $w$.

Entrada

La primera línea contiene $N$ ($2 \le N \le 100{,}000$).

Las siguientes $N-1$ líneas contienen dos enteros $u$ y $v$ que representan los extremos de la arista $i$.

La siguiente línea contiene los colores de los vértices $1$ a $N$. El color es $0$ o $1$, donde $0$ representa negro y $1$ representa blanco.

La siguiente línea contiene los pesos de los vértices $1$ a $N$ en orden.

La siguiente línea contiene el número de consultas $M$ ($1 \le M \le 100{,}000$).

Las siguientes $M$ líneas contienen una consulta cada una.

Todos los pesos son números naturales menores o iguales a $10^9$.

Salida

Imprimir los resultados de cada consulta de tipo $2$ en orden, cada uno en una línea.

Ejemplos

Entrada 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

Salida 1

1
5

Entrada 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

Salida 2

7
5
7