有 $N$ 个顶点构成的树（无向无环连通图）。顶点编号为 $1$ 至 $N$，边编号为 $1$ 至 $N-1$。每个顶点有黑色或白色两种颜色，并带有一个权值。

请编写一个程序执行以下三种查询：

• 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$ 行，每行两个整数 $u$ 和 $v$，表示第 $i$ 条边连接的两个顶点。

下一行包含 $N$ 个整数，表示第 $1$ 到第 $N$ 个顶点的颜色。颜色为 $0$ 或 $1$，$0$ 表示黑色，$1$ 表示白色。

再下一行包含 $N$ 个整数，依次表示第 $1$ 到第 $N$ 个顶点的权值。

下一行包含一个整数 $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