Calculate! 2

시간 제한1초메모리 제한512 MB

요약

루트가 있는 트리에서 부분 트리 XOR 질의와 부분 트리 XOR 갱신을 처리하며, 정점과 자손들의 XOR 값을 출력한다.

문제

제3회 IUPC의 Calculate!에서 교정이는 인규가 낸 논리 연산 문제를 모두 맞혔다. 1년 뒤에 제4회 IUPC가 열렸고, 인규는 이번에는 교정이를 꼭 골탕 먹이겠다는 생각으로 교정이가 빠르게 답하지 못할 어려운 논리 연산 문제를 준비했다.

인규가 준비한 문제는 다음과 같다.

정점이 $N$ 개인 트리가 주어진다. 루트는 항상 1번 정점이다. 트리는 정점 $N$ 개와 간선 $N-1$ 개로 이루어진, 사이클이 없는 연결 그래프다.
각 정점에는 가중치 $D$ 가 하나씩 붙어 있다.
질의 $M$ 개를 주어진 순서대로 처리한다.
1 x 꼴의 질의는 정점 $x$ 와 $x$ 의 모든 자손의 가중치를 전부 XOR한 값을 출력한다.
2 x y 꼴의 질의는 정점 $x$ 와 $x$ 의 모든 자손의 가중치에 각각 $y$ 를 XOR한다.

교정이의 답이 맞는지 확인하려고 한다. 1 x 꼴의 질의에 대한 답을 출력하는 프로그램을 작성하시오.

첫째 줄에 정점의 수 $N$ ( $3 \le N \le 100\,000$ )과 질의의 수 $M$ ( $3 \le M \le 500\,000$ )이 주어진다.

이어지는 $N-1$ 개의 줄에 두 정수 $A$ 와 $B$ 가 주어진다. 정점 $A$ 와 정점 $B$ 가 간선으로 연결되어 있다는 뜻이다.

다음 줄에 공백으로 구분된 $N$ 개의 수가 주어진다. $i$ 번째 수는 $i$ 번 정점의 가중치 $D_i$ ( $0 \le D_i \le 10\,000$ )다.

이후 $M$ 개의 줄에 질의가 한 줄에 하나씩 주어진다. 질의는 1 x 또는 2 x y 꼴이고, $1 \le x \le N$ 이며 $0 \le y \le 10\,000$ 이다.

1 x 꼴의 질의마다 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

예제 1

입력

예상 출력

1
90

예제 2

입력

7 10
1 2
1 3
1 4
4 5
4 6
6 7
49 38 29 40 3 59 0
2 7 45
2 3 30
1 7
1 5
1 1
2 1 2
1 4
2 6 15
1 1
1 2

예상 출력