Calculate! 2

At Calculate! in the 3rd IUPC, Gyojeong answered every logic operation question that Ingyu asked. The 4th IUPC was held a year later, and this time Ingyu wanted to trip Gyojeong up, so he prepared a hard logic operation problem that Gyojeong cannot answer quickly.

The problem Ingyu prepared is the following.

• A tree with $N$ vertices is given. The root is always vertex 1. A tree is a connected graph with $N$ vertices and $N-1$ edges and no cycle.
• Each vertex carries one weight $D$.
• $M$ queries are processed in the order they are given.
• A query of the form 1 x prints the XOR of the weights of vertex $x$ and all descendants of $x$.
• A query of the form 2 x y XORs $y$ into the weight of vertex $x$ and into the weight of every descendant of $x$.

Gyojeong's answers have to be checked. Write a program that prints the answer to every query of the form 1 x.

The first line contains the number of vertices $N$ ($3 \le N \le 100\,000$) and the number of queries $M$ ($3 \le M \le 500\,000$).

Each of the next $N-1$ lines contains two integers $A$ and $B$, which means that vertex $A$ and vertex $B$ are joined by an edge.

The next line contains $N$ numbers separated by spaces. The $i$-th number is the weight $D_i$ ($0 \le D_i \le 10\,000$) of vertex $i$.

Each of the next $M$ lines contains one query, either 1 x or 2 x y, with $1 \le x \le N$ and $0 \le y \le 10\,000$.

For every query of the form 1 x, print the answer on its own line, in the order the queries are given.