Jungol

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 (2 \leq N \leq 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 i 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 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.Problem credits: Charles Bailey

입력

The first line of input contains

N

and a 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 in terms of two integer attraction IDs

a

and

b

(both in the range

1 \ldots N

). Finally, 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

" indicates that

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 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$ .

예제1

출처

USACO 2019 February Gold

#4108

Cow Land 2초 512MB

문제

입력

출력

예제1

출처

역링크 공식 문제집만

#4108 upload -회 done -회 how_to_reg -명

Cow Land timer 2초 memory 512MB

문제 picture_in_picture_alt text_fields

입력

출력

예제1

출처

역링크 공식 문제집만

#4108

Cow Land 2초 512MB

문제