Calculate! 2

제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 꼴의 질의마다 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.