1 var t:array[0..8000000]of record
  2                            l,r,s:longint;
  3                           end;
  4     f:array[0..210000,0..18]of longint;
  5     head,vet,next,st,ed,dep,flag,hash,root1,root2,b:array[0..210000]of longint;
  6     d:array[0..210000,1..3]of longint;
  7     a:array[0..210000]of longint;
  8     q1,q2:array[0..80000]of longint;
  9     n,m,i,j,tot,time,up,la,lb,cnt,q,x,y,tmp,p,sum,z,f1,f2,f3,f4:longint;
 10 
 11 procedure add(a,b:longint);
 12 begin
 13  inc(tot);
 14  next[tot]:=head[a];
 15  vet[tot]:=b;
 16  head[a]:=tot;
 17 end;
 18 
 19 function max(x,y:longint):longint;
 20 begin
 21  if x>y then exit(x);
 22  exit(y);
 23 end;
 24 
 25 procedure swap(var x,y:longint);
 26 var t:longint;
 27 begin
 28  t:=x; x:=y; y:=t;
 29 end;
 30 
 31 function find(x:longint):longint;
 32 var l,r,mid:longint;
 33 begin
 34  l:=1; r:=up;
 35  while l<=r do
 36  begin
 37   mid:=(l+r)>>1;
 38   if hash[mid]=x then exit(mid);
 39   if hash[mid]<x then l:=mid+1
 40    else r:=mid-1;
 41  end;
 42 end;
 43 
 44 procedure update(l,r:longint;var p:longint;v,x:longint);
 45 var mid:longint;
 46 begin
 47  inc(cnt); t[cnt]:=t[p];
 48  p:=cnt; t[p].s:=t[p].s+x;
 49  if l=r then exit;
 50  mid:=(l+r)>>1;
 51  if v<=mid then update(l,mid,t[p].l,v,x)
 52   else update(mid+1,r,t[p].r,v,x);
 53 end;
 54 
 55 procedure dfs(u:longint);
 56 var e,v,i,tmp:longint;
 57 begin
 58  for i:=1 to 18 do
 59  begin
 60   if dep[u]<(1<<i) then break;
 61   f[u,i]:=f[f[u,i-1],i-1];
 62  end;
 63  tmp:=find(a[u]);
 64  root1[u]:=root1[f[u,0]];
 65  update(1,up,root1[u],tmp,1);
 66  inc(time); st[u]:=time; ed[u]:=time;
 67  flag[u]:=1;
 68  e:=head[u];
 69  while e<>0 do
 70  begin
 71   v:=vet[e];
 72   if flag[v]=0 then
 73   begin
 74    f[v,0]:=u;
 75    dep[v]:=dep[u]+1;
 76    dfs(v);
 77    ed[u]:=max(ed[u],ed[v]);
 78   end;
 79   e:=next[e];
 80  end;
 81 end;
 82 
 83 function lca(x,y:longint):longint;
 84 var d,i:longint;
 85 begin
 86  if dep[x]<dep[y] then swap(x,y);
 87  d:=dep[x]-dep[y];
 88  for i:=0 to 18 do
 89   if d and (1<<i)>0 then x:=f[x,i];
 90  for i:=18 downto 0 do
 91   if f[x,i]<>f[y,i] then
 92   begin
 93    x:=f[x,i]; y:=f[y,i];
 94   end;
 95  if x=y then exit(x);
 96  exit(f[x,0]);
 97 end;
 98 
 99 procedure qsort(l,r:longint);
100 var i,j,mid:longint;
101 begin
102  i:=l; j:=r; mid:=b[(l+r)>>1];
103  repeat
104   while mid>b[i] do inc(i);
105   while mid<b[j] do dec(j);
106   if i<=j then
107   begin
108    swap(b[i],b[j]);
109    inc(i); dec(j);
110   end;
111  until i>j;
112  if l<j then qsort(l,j);
113  if i<r then qsort(i,r);
114 end;
115 
116 function lowbit(x:longint):longint;
117 begin
118  exit(x and (-x));
119 end;
120 
121 function query(l,r,k:longint):longint;
122 var s1,s2,i,mid:longint;
123 begin
124  if l=r then exit(l);
125  mid:=(l+r)>>1;
126  s1:=0; s2:=0;
127  for i:=1 to la do s1:=s1+t[t[q1[i]].l].s;
128  for i:=1 to lb do s2:=s2+t[t[q2[i]].l].s;
129  s2:=s2+t[t[f1].l].s+t[t[f2].l].s;
130  s1:=s1+t[t[f3].l].s+t[t[f4].l].s;
131  if s2-s1>=k then
132  begin
133   f1:=t[f1].l; f2:=t[f2].l;
134   f3:=t[f3].l; f4:=t[f4].l;
135   for i:=1 to la do q1[i]:=t[q1[i]].l;
136   for i:=1 to lb do q2[i]:=t[q2[i]].l;
137   exit(query(l,mid,k));
138  end
139   else
140   begin
141    f1:=t[f1].r; f2:=t[f2].r;
142    f3:=t[f3].r; f4:=t[f4].r;
143    for i:=1 to la do q1[i]:=t[q1[i]].r;
144    for i:=1 to lb do q2[i]:=t[q2[i]].r;
145    exit(query(mid+1,r,k-(s2-s1)));
146   end;
147 end;
148 
149 begin
150  assign(input,‘data.in‘); reset(input);
151  assign(output,‘tyvj2133.out‘); rewrite(output);
152  read(n,m);
153  for i:=1 to n do
154  begin
155   read(a[i]); b[i]:=a[i];
156  end;
157  q:=n;
158  for i:=1 to n-1 do
159  begin
160   read(x,y);
161   add(x,y);
162   add(y,x);
163  end;
164 
165  for i:=1 to m do
166   for j:=1 to 3 do read(d[i,j]);
167  for i:=1 to m do
168   if d[i,1]=0 then
169   begin
170    inc(q); b[q]:=d[i,3];
171   end;
172  qsort(1,q);
173  hash[1]:=b[1]; up:=1;
174  for i:=2 to q do
175   if b[i]<>b[i-1] then begin inc(up); hash[up]:=b[i]; end;
176  dfs(1);
177 
178 
179  for i:=1 to m do
180   if d[i,1]=0 then
181   begin
182    tmp:=find(a[d[i,2]]);
183    j:=st[d[i,2]];
184    while j<=n do
185    begin
186     update(1,up,root2[j],tmp,-1);
187     j:=j+lowbit(j);
188    end;
189    j:=ed[d[i,2]]+1;
190    while j<=n do
191    begin
192     update(1,up,root2[j],tmp,1);
193     j:=j+lowbit(j);
194    end;
195    tmp:=find(d[i,3]);
196    j:=st[d[i,2]];
197    while j<=n do
198    begin
199     update(1,up,root2[j],tmp,1);
200     j:=j+lowbit(j);
201    end;
202    j:=ed[d[i,2]]+1;
203    while j<=n do
204    begin
205     update(1,up,root2[j],tmp,-1);
206     j:=j+lowbit(j);
207    end;
208 
209    a[d[i,2]]:=d[i,3];
210   end
211    else
212    begin
213     la:=0; lb:=0; p:=lca(d[i,2],d[i,3]);
214     j:=st[d[i,2]];
215     while j>0 do
216     begin
217      inc(lb); q2[lb]:=root2[j];
218      j:=j-lowbit(j);
219     end;
220 
221     j:=st[d[i,3]];
222     while j>0 do
223     begin
224      inc(lb); q2[lb]:=root2[j];
225      j:=j-lowbit(j);
226     end;
227 
228     j:=st[p];
229     while j>0 do
230     begin
231      inc(la); q1[la]:=root2[j];
232      j:=j-lowbit(j);
233     end;
234 
235     j:=st[f[p,0]];
236     while j>0 do
237     begin
238      inc(la); q1[la]:=root2[j];
239      j:=j-lowbit(j);
240     end;
241 
242     f1:=root1[d[i,2]]; f2:=root1[d[i,3]];
243     f3:=root1[p]; f4:=root1[f[p,0]];
244     sum:=dep[d[i,2]]+dep[d[i,3]]-dep[p]*2+1;
245     z:=sum-d[i,1]+1;
246     if sum<d[i,1] then writeln(‘invalid request!‘)
247      else writeln(hash[query(1,up,z)]);
248    end;
249 
250 
251  close(input);
252  close(output);
253 end.