$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$개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v가 주어진다.

다음 줄에는 $1$번 정점부터 $N$번 정점까지 색이 주어진다. 색은 $0$ 또는 $1$이며, $0$은 검정색, $1$은 흰색을 나타낸다. 그 다음 줄에는 각 정점의 가중치가 $1$번 정점부터 순서대로 주어진다.

다음 줄에는 쿼리의 개수 $M$ ($1 \le M \le 100{,}000$)이 주어진다.

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

모든 가중치는 $10^9$보다 작거나 같은 자연수이다.

출력

각각의 $2$번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

Sample

Input

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
5

Sample

Input

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

7
5
7