Cow Land là công viên giải trí đặc biệt cho bò: chúng đi dạo, ăn cỏ ngon và thăm nhiều trò chơi (tàu lượn dành cho bò đặc biệt phổ biến).

Có $N$ điểm vui chơi khác nhau ($2 \leq N \leq 10^5$). Một số cặp được nối bằng đường, tổng cộng $N-1$ đường, sao cho giữa hai điểm bất kỳ có duy nhất một tuyến gồm các đường này. Mỗi điểm $i$ có giá trị vui thích nguyên $e_i$, có thể đổi trong ngày vì một số hấp dẫn hơn buổi sáng, số khác vào cuối buổi chiều.

Bò đi từ $i$ đến $j$ sẽ trải nghiệm mọi điểm trên tuyến từ $i$ đến $j$. Lạ thay, tổng vui thích là XOR theo bit của tất cả giá trị trên tuyến, kể cả $i$ và $j$.

Hãy giúp bò tính vui thích của các tuyến định đi trong lần thăm Cow Land tiếp theo.

Dữ liệu vào

Dòng đầu chứa $N$ và số truy vấn $Q$ ($1 \leq Q \leq 10^5$). Dòng tiếp chứa $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). $N-1$ dòng sau mô tả đường bằng hai mã điểm nguyên $a$ và $b$ (đều trong $1 \ldots N$). $Q$ dòng cuối mô tả cập nhật $e_i$ hoặc truy vấn vui thích tuyến. "1 $i$ $v$" cập nhật $e_i$ thành $v$; "2 $i$ $j$" hỏi vui thích tuyến giữa $i$ và $j$.

Trong dữ liệu kiểm tra trị giá tối đa 50% số điểm, giá trị các điểm vui chơi không đổi.

Dữ liệu ra

Với mỗi truy vấn "2 $i$ $j$", in vui thích tuyến từ $i$ đến $j$ trên một dòng.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

21
20
4
20

Tác giả bài toán: Charles Bailey