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$까지 경로의 즐거움을 한 줄에 출력하세요.

예제

입력 1

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

출력 1

21
20
4
20

문제 출제자: Charles Bailey