from collections import defaultdict from typing import Callable import operator import typing def _ceil_pow2(n: int) -> int: x = 0 while (1 << x) < n: x += 1 return x class SegTree: def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any], e: typing.Any, v: typing.Union[int, typing.List[typing.Any]]) -> None: self._op = op self._e = e if isinstance(v, int): v = [e] * v self._n = len(v) self._log = _ceil_pow2(self._n) self._size = 1 << self._log self._d = [e] * (2 * self._size) for i in range(self._n): self._d[self._size + i] = v[i] for i in range(self._size - 1, 0, -1): self._update(i) def set(self, p: int, x: typing.Any) -> None: assert 0 <= p < self._n p += self._size self._d[p] = x for i in range(1, self._log + 1): self._update(p >> i) def get(self, p: int) -> typing.Any: assert 0 <= p < self._n return self._d[p + self._size] def prod(self, left: int, right: int) -> typing.Any: assert 0 <= left <= right <= self._n sml = self._e smr = self._e left += self._size right += self._size while left < right: if left & 1: sml = self._op(sml, self._d[left]) left += 1 if right & 1: right -= 1 smr = self._op(self._d[right], smr) left >>= 1 right >>= 1 return self._op(sml, smr) def all_prod(self) -> typing.Any: return self._d[1] def max_right(self, left: int, f: typing.Callable[[typing.Any], bool]) -> int: assert 0 <= left <= self._n assert f(self._e) if left == self._n: return self._n left += self._size sm = self._e first = True while first or (left & -left) != left: first = False while left % 2 == 0: left >>= 1 if not f(self._op(sm, self._d[left])): while left < self._size: left *= 2 if f(self._op(sm, self._d[left])): sm = self._op(sm, self._d[left]) left += 1 return left - self._size sm = self._op(sm, self._d[left]) left += 1 return self._n def min_left(self, right: int, f: typing.Callable[[typing.Any], bool]) -> int: assert 0 <= right <= self._n assert f(self._e) if right == 0: return 0 right += self._size sm = self._e first = True while first or (right & -right) != right: first = False right -= 1 while right > 1 and right % 2: right >>= 1 if not f(self._op(self._d[right], sm)): while right < self._size: right = 2 * right + 1 if f(self._op(self._d[right], sm)): sm = self._op(self._d[right], sm) right -= 1 return right + 1 - self._size sm = self._op(self._d[right], sm) return 0 def _update(self, k: int) -> None: self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1]) class HLD: def __init__(self, n: int, adj: dict[int, list[int]], root=0): """ n: 頂点数 adj: {頂点: [隣接頂点, ...]} root: 根 """ self.n = n self.vid = [-1] * n self.inv = [0] * n self.par = [-1] * n self.depth = [0] * n self.subsize = [1] * n self.head = [0] * n self.prev = [-1] * n self.next = [-1] * n self.types = [0] * n self._build([root], adj) def _build(self, roots, adj): pos = 0 for i, root in enumerate(roots): self._decide_heavy_edge(root, adj) pos = self._reconstruct(root, i, pos, adj) def _decide_heavy_edge(self, root: int, adj): """部分木サイズを計算し、heavy edge を決定""" st = [(root, 0)] self.par[root] = -1 self.depth[root] = 0 while st: v, i = st[-1] if i < len(adj[v]): to = adj[v][i] st[-1] = (v, i+1) if to == self.par[v]: continue self.par[to] = v self.depth[to] = self.depth[v] + 1 st.append((to, 0)) else: st.pop() maxsize = 0 for to in adj[v]: if to == self.par[v]: continue self.subsize[v] += self.subsize[to] if self.subsize[to] > maxsize: maxsize = self.subsize[to] self.prev[to] = v self.next[v] = to def _reconstruct(self, root: int, curtype: int, pos: int, adj): """heavy-pathごとに Euler順 vid を割り当てる""" st = [root] while st: start = st.pop() v = start while v != -1: self.types[v] = curtype self.vid[v] = pos self.inv[pos] = v self.head[v] = start pos += 1 # 軽辺の子はあとでstackに積む for to in adj[v]: if to != self.par[v] and to != self.next[v]: st.append(to) v = self.next[v] return pos def foreach_nodes(self, u: int, v: int, f: Callable[[int, int], None]): """頂点 u, v 間の頂点区間に対してコールバック [l, r] を呼ぶ""" while True: if self.vid[u] > self.vid[v]: u, v = v, u f(max(self.vid[self.head[v]], self.vid[u]), self.vid[v]) if self.head[u] != self.head[v]: v = self.par[self.head[v]] else: break # u-v間の辺区間に対してコールバックを呼ぶ def foreach_edges(self, u: int, v: int, f: Callable[[int, int], None]): """頂点 u, v 間の辺区間に対してコールバック [l, r] を呼ぶ""" while True: if self.vid[u] > self.vid[v]: u, v = v, u if self.head[u] != self.head[v]: f(self.vid[self.head[v]], self.vid[v]) v = self.par[self.head[v]] else: if u != v: f(self.vid[u]+1, self.vid[v]) break def lca(self, u: int, v: int) -> int: while True: if self.vid[u] > self.vid[v]: u, v = v, u if self.head[u] == self.head[v]: return u v = self.par[self.head[v]] class VertexWeightedSubtreeXorHLD: def __init__(self, n: int, adj: dict[int, list[int]], costs: list[int]): """ n: 頂点数 adj: {頂点: [隣接頂点, ...]} wmap: wmap[u, v] = 頂点 u, v 間の辺の重み """ hld = HLD(n, adj, root=0) segt = SegTree(operator.xor, 0, n) for i, c in enumerate(costs): segt.set(hld.vid[i], c) self.n = n self.hld = hld self.segt = segt def apply_xor(self, v: int, x: int): """頂点 v の値に xor x を適用する""" p = self.hld.vid[v] self.segt.set(p, self.segt.get(p) ^ x) def query_xor(self, v: int) -> int: """頂点 v を根とする部分木の全ての頂点の xor を求める""" l = self.hld.vid[v] r = self.hld.vid[v] + self.hld.subsize[v] - 1 if l > r: return res return self.segt.prod(l, r+1) N, Q = map(int, input().split()) C = list(map(int, input().split())) adj = defaultdict(list) for _ in range(N-1): u, v = map(lambda x: int(x)-1, input().split()) adj[u].append(v) adj[v].append(u) hld = VertexWeightedSubtreeXorHLD(N, adj, C) for _ in range(Q): qs = list(map(int, input().split())) match qs: case (1, x, y): # 頂点 x の値に対して xor y を適用する x -= 1 hld.apply_xor(x, y) case (2, x, y): # 頂点 x を根とする部分木の全ての値の xor を求める assert y == 0 x -= 1 res = hld.query_xor(x) print(res)