Cow Land

Cow Land is a special amusement park for cows. They roam around, eat delicious grass, and visit the various cow attractions (the roller cowster is especially popular).

There are $N$ attractions in total ($2 \leq N \leq 10^5$). Some pairs of attractions are connected by pathways, $N-1$ in total, so that a unique route made up of pathways exists between any two attractions. Attraction $i$ has an integer enjoyment value $e_i$. This value can change over the course of a day, since some attractions are more appealing in the morning and others later in the afternoon.

A cow that travels from attraction $i$ to attraction $j$ experiences every attraction on the route from $i$ to $j$. Curiously, the enjoyment of this entire route is the bitwise XOR of all the enjoyment values along the route, including those of attractions $i$ and $j$.

Help the cows determine the enjoyment values of the routes they plan to use on their next trip to Cow Land.

The first line contains $N$ and the number of queries $Q$ ($1 \leq Q \leq 10^5$). The next line contains $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). The next $N-1$ lines each describe a pathway with two integer attraction IDs $a$ and $b$ (both in the range $1 \ldots N$). The last $Q$ lines each describe either an update to one of the $e_i$ values or a query for the enjoyment of a route. A line of the form "1 $i$ $v$" means $e_i$ should be updated to value $v$, and a line of the form "2 $i$ $j$" is a query for the enjoyment of the route connecting attractions $i$ and $j$.

In test data worth at most 50% of the points, the attraction values never change.

For each query of the form "2 $i$ $j$", print the enjoyment of the route from $i$ to $j$ on a single line.