There are a total of N different attractions (2≤N≤10^5). 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 ii has an integer enjoyment value ei, 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 i to attraction j gets to experience all the attractions on the route from i to j. 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 i and j.
Please help the cows determine the enjoyment values of the routes they plan to use during their next trip to Cow Land.
The first line of input contains N and a number of queries Q (1≤Q≤10^5). The next line contains e1…eN (0≤ei≤10^9). The next N−1 lines each describe a pathway in terms of two integer attraction IDs a and b (both in the range 1…N). Finally, the last Q lines each describe either an update to one of the ei values or a query for the enjoyment of a route. A line of the form "1 i v" indicates that ei should be updated to value v, and a line of the form "2i j" is a query for the enjoyment of the route connecting attractions i and j.
In test data worth at most 50% of points, there will be no changes to the values of the attractions.
For each query of the form "2 i j", print on a single line the enjoyment of the route from i to j.