Cho một cây (đồ thị vô hướng, liên thông, không có chu trình) gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Mỗi đỉnh có màu đen hoặc trắng và có một trọng số.

Hãy viết chương trình thực hiện ba loại truy vấn sau:

• 1 i: Đổi màu của đỉnh thứ $i$. (trắng → đen, đen → trắng)
• 2 u: Tìm đỉnh $v$ có trọng số lớn nhất trong số các đỉnh được kết nối với $u$. Hai đỉnh được coi là kết nối nếu mọi đỉnh trên đường đi giữa chúng đều có cùng màu. Lưu ý rằng $u$ có thể bằng $v$.
• 3 u w: Thay đổi trọng số của đỉnh $u$ thành $w$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100{,}000$).

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên u và v là hai đầu mút của cạnh thứ $i$.

Dòng tiếp theo chứa màu của các đỉnh từ $1$ đến $N$. Màu là $0$ hoặc $1$, trong đó $0$ là màu đen, $1$ là màu trắng.

Dòng tiếp theo chứa trọng số của các đỉnh theo thứ tự từ $1$ đến $N$.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Tất cả trọng số đều là số tự nhiên nhỏ hơn hoặc bằng $10^9$.

Dữ liệu ra

Đối với mỗi truy vấn loại $2$, in ra kết quả trên một dòng, theo đúng thứ tự xuất hiện.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
5

Dữ liệu vào 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

Dữ liệu ra 2

7
5
7