Cow Land#10347
Cow Land is a special amusement park for cows, where they roam around, eat delicious grass, and visit different cow attractions (the roller cowster is particularly popular).
There are a total of different attractions. Certain pairs of attractions are connected by pathways, n - 1 in total, in such a way that there is a unique route consisting of various pathways between any two attractions. Each attraction has an integer enjoyment value e_i, which 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 to attraction gets to experience all the attractions on the route from to . Curiously, the total enjoyment value of this entire route is given by the bitwise XOR of all the enjoyment values along the route, including those of attractions and .
Help the cows determine the enjoyment values of the routes they plan to use during their next trip to Cow Land.
The first line contains (2 \le n \le 10^5) and a number of queries (1 \le q \le 10^5). The next line contains e_1, \ldots, e_n (0 \le e_i \le 10^9). The next n - 1 lines each describe a pathway in terms of two integer attraction IDs and (both in the range 1, \ldots, n). Finally, the last 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" indicates that e_i should be updated to value , and a line of the form "2 i j" is a query for the enjoyment of the route connecting attractions and .
For each query of the form "2 i j", print on a single line the enjoyment of the route from to .
Example 1