같은 색으로 이어진 정점의 최대 가중치

N개의 정점으로 이루어진 트리(사이클이 없는 연결 무향 그래프)가 있다. 정점에는 1번부터 N번까지, 간선에는 1번부터 N-1번까지 번호가 붙어 있다. 각 정점의 색은 검은색 또는 흰색이고, 각 정점에는 자연수 가중치가 있다.

두 정점 u와 v가 이어져 있다는 것은 u에서 v로 가는 경로에 놓인 모든 정점의 색이 같다는 뜻이다. u와 v는 같은 정점일 수도 있다.

다음 세 가지 쿼리를 처리하는 프로그램을 작성하시오.

• 1 i: i번 정점의 색을 바꾼다. 흰색은 검은색으로, 검은색은 흰색으로 바뀐다.
• 2 u: u와 이어져 있는 정점 중에서 가중치가 가장 큰 값을 출력한다.
• 3 u w: u번 정점의 가중치를 w로 바꾼다.

첫째 줄에 정점의 개수 N이 주어진다. (2 ≤ N ≤ 100,000)

다음 N-1개의 줄에는 i번 간선이 잇는 두 정점의 번호 u와 v가 주어진다.

다음 줄에는 1번 정점부터 N번 정점까지의 색이 순서대로 주어진다. 색은 0 또는 1이며, 0은 검은색, 1은 흰색이다.

다음 줄에는 1번 정점부터 N번 정점까지의 가중치가 순서대로 주어진다.

다음 줄에는 쿼리의 개수 M이 주어진다. (1 ≤ M ≤ 100,000)

이어지는 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다.

모든 가중치는 $10^9$ 이하의 자연수이고, 3번 쿼리의 w도 그렇다.

2번 쿼리의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.