#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxn=8e4+10;
int n,q,la[mxn];
vector<int> e[mxn];
int dep[mxn],son[mxn],sz[mxn],fa[mxn];
void dfs1(int x,int xfa){
	dep[x]=dep[xfa]+1;
	son[x]=-1;
	sz[x]=1;
	fa[x]=xfa;
	for(int y:e[x])if(y!=xfa){
		dfs1(y,x);
		sz[x]+=sz[y];
		if(son[x]==-1||sz[y]>sz[son[x]])son[x]=y;
	} 
}
int dfn[mxn],_dfn[mxn],top[mxn],tsp;
void dfs2(int x,int tp){
	top[x]=tp;
	dfn[x]=++tsp;
	_dfn[tsp]=x;
	if(~son[x]){
		dfs2(son[x],tp);
		for(int y:e[x])if(y!=fa[x]&&y!=son[x]){
			dfs2(y,y);
		}
	}
}
int lowbit(int x){
	return x&(-x);
}
struct BIT{
	int tr[mxn];
	void add(int x,int v){
		for(int i=x;i<=n;i+=lowbit(i)){
			tr[i]+=v;
		}
	}
	int find(int x){
		int ans=0;
		for(int i=x;i;i-=lowbit(i)){
			ans+=tr[i]; 
		}
		return ans;
	}
}tr;
int find(int x,int y){
	int ans=0;
	for(;top[x]!=top[y];x=fa[top[x]]){
		if(dep[top[x]]<dep[top[y]])x^=y^=x^=y;
		ans+=tr.find(dfn[x])-tr.find(dfn[top[x]]-1);
	}
	if(dfn[x]>dfn[y])x^=y^=x^=y;
	ans+=tr.find(dfn[y])-tr.find(dfn[x]-1);
	return ans;
}
struct Q{
	int x,y,k,id;
}qq[350010],u1[350010],u2[350010];
int ans[100010],lsh[200010];
void solve(int l,int r,int x,int y){
	if(l==r){
		for(int i=x;i<=y;i++){
			ans[qq[i].id]=lsh[l];
		}
		return ;
	}
	int mid=(l+r+1)>>1,n1=0,n2=0;
	for(int i=x;i<=y;i++){
		if(!qq[i].id){
      if(qq[i].y>=mid)tr.add(dfn[qq[i].x],qq[i].k),u2[++n2]=qq[i];
			else u1[++n1]=qq[i];
		}
		else{
			int v=find(qq[i].x,qq[i].y);
			if(v>=qq[i].k)u2[++n2]=qq[i];
			else qq[i].k-=v,u1[++n1]=qq[i];
		}
	}
	for(int i=1;i<=n2;i++)if(!u2[i].id)tr.add(dfn[u2[i].x],-u2[i].k);
	int id=x;
	for(int i=1;i<=n1;i++)qq[id++]=u1[i];
	for(int i=1;i<=n2;i++)qq[id++]=u2[i];
	solve(l,mid-1,x,x+n1-1);
	solve(mid,r,x+n1,y);
}
int main(){
	 ios::sync_with_stdio(0);
	 cin.tie(0);
	cin>>n>>q;
	int cnt=0;
	for(int i=1;i<=n;i++){
		cin>>la[i];
		qq[++cnt]={i,la[i],1,0};
		lsh[i]=la[i];
	}
	int ln=n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,1);
	int qqi=0;
	for(int i=1;i<=q;i++){
		int k,x,y;
		cin>>k>>x>>y;
		if(!k){
			qq[++cnt]={x,la[x],-1,0};
			qq[++cnt]={x,y,1,0};
			la[x]=y;
			lsh[++ln]=y;
		}
		else{
			qq[++cnt]={x,y,k,++qqi};
		}
	}
	sort(lsh+1,lsh+1+ln);
	ln=unique(lsh+1,lsh+1+ln)-lsh-1;
	for(int i=1;i<=cnt;i++){
		if(!qq[i].id){
			qq[i].y=lower_bound(lsh+1,lsh+1+ln,qq[i].y)-lsh;
		}
	}
	solve(0,ln,1,cnt);
	for(int i=1;i<=qqi;i++){
		if(ans[i])cout<<ans[i]<<'\n';
		else cout<<"invalid request!\n";
	}
	return 0;
}