15782번 - Calculate! 2

문제

제 3회 IUPC의 Calculate! 에서 교정이는 인규가 질문한 모든 논리연산에 대한 정답을 말하였다. 그 후 1년 뒤 제 4회 IUPC가 열리게 되었고, 인규는 이번에는 교정이를 꼭 골탕 먹이겠다는 생각을 갖고 교정이가 빠르게 대답을 못할만한 어려운 논리연산 문제를 준비했다.

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

• 정점이 N(≤ 100,000)개인 트리가 주어진다. 루트는 항상 1번 정점이다. (트리란 N개의 정점과 N-1개의 간선으로 이루어 진 사이클이 존재하지 않는 하나의 컴포넌트를 가지는 연결 그래프이다)
• 각 정점은 가중치 D(0 ≤ D ≤ 10,000)를 가진다.
• M(≤ 500,000)개의 질의가 주어진다.
• 1 x 꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치를 전부 XOR한 값을 출력.
• 2 x y 꼴로 주어지는 질의에는 정점 x를 포함한 x의 모든 자손들의 가중치에 각각 y(0 ≤ y ≤ 10,000)를 XOR을 함.

인규의 문제에 대한 교정이의 답변이 맞는지 확인하기 위하여 1 x 꼴로 주어지는 질의에 대한 답을 출력하는 프로그램을 작성해보자

입력

입력의 첫째 줄에 정점의 수 N(3 ≤ N ≤ 100,000)와 질의의 수 M(3 ≤ M ≤ 500,000)이 주어진다. 이 후 N-1줄에 A,B가 주어진다. 이는 A와 B가 연결되어 있다는 뜻이다. 다음 줄에 공백으로 분리 된 N개의 수가 주어진다. i번 째 수는 i번 째 정점의 가중치를 의미한다. 이후 M개의 줄에 질의가 주어진다.

출력

M개의 질의 중, 1 x 꼴로 주어지는 질의에 대한 답을 한줄 씩 출력한다.

제한

힌트