Cow Land 是專為乳牛設計的遊樂園，牠們能四處漫步、吃美味的草、體驗不同的乳牛遊樂設施（乳牛雲霄飛車尤其受歡迎）。

共有 $N$ 個不同設施（$2 \leq N \leq 10^5$）。某些設施由道路連接，共 $N-1$ 條，且任意兩座設施之間都有唯一一條由這些道路組成的路線。設施 $i$ 的整數快樂值為 $e_i$，一天中可能變化，因為有些設施早晨更吸引人，有些下午較晚時更吸引人。

從設施 $i$ 前往 $j$ 的乳牛會體驗從 $i$ 到 $j$ 路線上的全部設施。奇妙的是，路線的總快樂值等於沿途所有快樂值的逐位互斥或，包括設施 $i$ 和 $j$ 的值。

請幫乳牛求出下次遊覽 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