class SegTree: #単位元と結合演算はここ変える #いろんな種類のsegは作れないかも #→changeで変えれる unit = 0 def f(self,x,y): return x ^ y #頂点は1-index、一番下の段は0-index(bitは1-index) def __init__(self,N): self.N = N self.X = [self.unit] * (N + N) def build(self,seq): for i,x in enumerate(seq,self.N): self.X[i] = x for i in range(self.N-1,0,-1): self.X[i] = self.f(self.X[i << 1],self.X[i << 1 | 1]) def set(self,i,x): i += self.N self.X[i] = x while i > 1: i >>= 1 self.X[i] = self.f(self.X[i << 1],self.X[i << 1 | 1]) def fold(self,L,R): #区間[L,R)についてfold #0 <= L,R <= N にしなきゃダメ L += self.N R += self.N vL = self.unit vR = self.unit while L < R: if L & 1: vL = self.f(vL,self.X[L]) L += 1 if R & 1: R -= 1 vR = self.f(self.X[R],vR) L >>= 1 R >>= 1 return self.f(vL,vR) def get(self,i): return self.X[i+self.N] def change(self,f,unit): self.f = f self.unit = unit #HL分解 class HL: #u,vを結ぶpathへのクエリはここにでも # f は区間 [l,r)に対するクエリ def f(self,l,r): pass def merge(self,x,y): return x + y def __init__(self,G,root): self.G = G self.root = root self.N = len(G) self.size = [1] * self.N #部分木のサイズ self.p = [0] * self.N #親頂点 self.H = [None] * self.N #Heavy_edgeでつながる子頂点。葉ではNoneが入ってる self._in = [-1] * self.N #最初に探索したときの位置 self.out = [-1] * self.N #部分木をでるタイミング。オイラーとはちょっと違う。 #開区間 [_in[i],out[i]) がiの部分木に対応 self.pathtop = [0] * self.N #iの属するpathの中で最も根に近い頂点。代表にする self.build() self.build_path() def build(self): stack = [(~self.root,-1),(self.root,-1)] G = self.G size = self.size H = self.H while stack: now,parent = stack.pop() if now < 0: now = ~now _max = 0 for v in G[now]: if v == parent:continue size[now] += size[v] if size[v] > _max: _max = size[v] H[now] = v else: for v in G[now]: if v == parent:continue self.p[v] = now stack.append((~v,now)) stack.append((v,now)) def build_path(self): stack = [(~self.root,-1,self.root),(self.root,-1,self.root)] count = 0 G = self.G H = self.H while stack: now,parent,top = stack.pop() if now >= 0: self._in[now] = count count += 1 self.pathtop[now] = top h = H[now] if h is None:continue for v in G[now]: if v == parent or v == h:continue stack.append((~v,now,v)) stack.append((v,now,v)) stack.append((~h,now,top)) stack.append((h,now,top)) else: now = ~now self.out[now] = count def lca(self,a,b): #最近共通先祖 pathtop = self.pathtop _in = self._in pa = pathtop[a] pb = pathtop[b] while pa != pb: if _in[pa] > _in[pb]: a = self.p[pa] pa = pathtop[a] else: b = self.p[pb] pb = pathtop[b] return a if _in[a] < _in[b] else b def subtree_query(self,a,f = None): #if f is None:f = self.f return f(self._in[a],self.out[a]) def subtree_array(self,a): return (self._in[a],self.out[a]) #下のpath_arrayとほぼ同じ。タプルを一つだけ返す #f = lambda l,r:seg.fold(l,r) とか #f = lambda l,r:seg.oparete_range(l,r,x) とか #代入して使う def path_query(self,a,b,f = None,merge = None): #if f is None:f = self.f #if merge is None:merge = self.merge pathtop = self.pathtop p = self.p _in = self._in pa = pathtop[a] pb = pathtop[b] ans = 0 while pa != pb: if _in[pa] > _in[pb]: ans = merge(ans,f(_in[pa],_in[a]+1)) a = p[pa] pa = pathtop[a] else: ans = merge(ans,f(_in[pb],_in[b]+1)) b = p[pb] pb = pathtop[b] if _in[a] > _in[b]: a,b = b,a ans = merge(ans,f(_in[a],_in[b]+1)) return ans def path_array(self,a,b): # a,b を結ぶpath、を分割した配列を返す。こっちのほうが便利かも #半開区間 [l,r) の集まりを返す #現状順番は適当 #こっちのほうが早かった pathtop = self.pathtop p = self.p _in = self._in ans = [] pa = pathtop[a] pb = pathtop[b] while pa != pb: if _in[pa] > _in[pb]: ans.append((_in[pa],_in[a]+1)) a = p[pa] pa = pathtop[a] else: ans.append((_in[pb],_in[b]+1)) b = p[pb] pb = pathtop[b] if _in[a] > _in[b]: a,b = b,a ans.append((_in[a],_in[b]+1)) return ans N,Q = map(int,input().split()) C = list(map(int,input().split())) G = [[] for _ in range(N)] for _ in range(N-1): a,b = map(int,input().split()) a -= 1 b -= 1 G[a].append(b) G[b].append(a) hl = HL(G,0) seq = [0] * N for i in range(N): seq[hl._in[i]] = C[i] seg = SegTree(N) seg.build(seq) for _ in range(Q): T,x,y = map(int,input().split()) x -= 1 if T == 1: a = seg.get(hl._in[x]) seg.set(hl._in[x],a^y) else: l,r = hl.subtree_array(x) print(seg.fold(l,r))