There is a tree (an undirected connected graph with no cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Each vertex has a color (black or white) and a weight.

Write a program that processes the following three types of queries:

• 1 i: Toggle the color of vertex $i$. (white $\to$ black, black $\to$ white)
• 2 u: Find and output the maximum weight among vertices $v$ that are connected to $u$. Two vertices are considered connected if all vertices on the path between them have the same color. Here, $u$ and $v$ can be the same vertex.
• 3 u w: Change the weight of vertex $u$ to $w$.

Input

The first line contains $N$ ($2 \le N \le 100{,}000$).

The next $N-1$ lines each contain two integers $u$ and $v$ — the vertices connected by the $i$-th edge.

The next line contains the colors of vertices from $1$ to $N$. The color is $0$ or $1$, where $0$ represents black and $1$ represents white. The next line contains the weight of each vertex in order from vertex $1$ to vertex $N$.

The next line contains the number of queries $M$ ($1 \le M \le 100{,}000$).

The next $M$ lines each contain a query.

All weights are natural numbers less than or equal to $10^9$.

Output

For each type-2 query, output the result on its own line, in the order they appear.

Examples

Input 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

Output 1

1
5

Input 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

Output 2

7
5
7