Cow Land
Cow Land
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 n 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 i 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.
Help the cows determine the enjoyment values of the routes they plan to use during their next trip to Cow Land.
Input
The first line contains n (2 ≤ n ≤ 105
) and a number of queries q (1 ≤ q ≤ 105
). The next line contains e1
...en
(0 ≤ ei
≤ 109
). 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 "2 i j" is a query for the enjoyment of the route connecting attractions i and j.
Output
For each query of the form "2 i j", print on a single line the enjoyment of the route from i to j.
5 5 1 2 4 8 16 1 2 1 3 3 4 3 5 2 1 5 1 1 16 2 3 5 2 1 5 2 1 3
21 20 4 20