Cow Land

Cow Land는 소를 위한 특별한 놀이공원이다. 소들은 이곳을 거닐고, 맛있는 풀을 먹고, 여러 소 명소를 찾아간다 (롤러코우스터가 특히 인기가 많다).

총 $N$개의 명소가 있다 ($2 \leq N \leq 10^5$). 일부 명소 쌍은 $N-1$개의 길로 연결되어 있어, 임의의 두 명소 사이에 여러 길로 이루어진 유일한 경로가 존재한다. 명소 $i$에는 정수 즐거움 값 $e_i$가 있다. 어떤 명소는 아침에 더 매력적이고 어떤 명소는 오후에 더 매력적이기 때문에, 이 값은 하루 동안 변할 수 있다.

명소 $i$에서 명소 $j$로 이동하는 소는 $i$에서 $j$까지의 경로에 있는 모든 명소를 체험한다. 흥미롭게도 이 경로 전체의 즐거움 값은 명소 $i$와 $j$의 값까지 포함하여 경로 위 모든 즐거움 값의 비트 XOR로 주어진다.

소들이 다음 Cow Land 여행에서 사용할 경로의 즐거움 값을 구할 수 있도록 도와주자.

첫째 줄에 $N$과 질의의 수 $Q$가 주어진다 ($1 \leq Q \leq 10^5$). 다음 줄에 $e_1 \ldots e_N$이 주어진다 ($0 \leq e_i \leq 10^9$). 다음 $N-1$개의 줄에는 길이 두 정수 명소 번호 $a$와 $b$로 주어진다 (둘 다 $1 \ldots N$ 범위). 마지막 $Q$개의 줄에는 $e_i$ 값 중 하나를 갱신하는 연산이나 경로의 즐거움을 묻는 질의가 주어진다. "1 $i$ $v$" 형태의 줄은 $e_i$를 값 $v$로 갱신해야 함을 나타내고, "2 $i$ $j$" 형태의 줄은 명소 $i$와 $j$를 잇는 경로의 즐거움을 묻는 질의이다.

전체 점수의 최대 50%에 해당하는 테스트 데이터에서는 명소의 값이 변하지 않는다.

"2 $i$ $j$" 형태의 질의마다 $i$에서 $j$까지의 경로의 즐거움을 한 줄에 출력한다.