#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstdlib>

#include <vector>

using namespace std;

const int N=80005;

struct Gragh{

	int cnt,y[N*2],nxt[N*2],fst[N];

	void clear(){

		cnt=0;

		memset(fst,0,sizeof fst);

	}

	void add(int a,int b){

		y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;

	}

}g;

struct cz{

	int k,a,b;

}q[N];

int n,Q,v[N],Ha[N*2],hs;

int fa[N],son[N],depth[N],size[N],top[N],p[N],ap[N],cnp=0;

const int S=N*2*2*20;

vector <int> val[N];

int ls[S],rs[S],root[N],Next[S],sum[S],pp[S],app[S],tot=0,tpp=0;

void LSH(){

	sort(Ha+1,Ha+hs+1);

	int hs_=1;

	for (int i=2;i<=hs;i++)

		if (Ha[i]!=Ha[i-1])

			Ha[++hs_]=Ha[i];

	hs=hs_;

}

void Get_Gen_Info(int rt,int pre,int d){

	fa[rt]=pre,depth[rt]=d,size[rt]=1,son[rt]=-1;

	for (int i=g.fst[rt];i;i=g.nxt[i])

		if (g.y[i]!=pre){

			int s=g.y[i];

			Get_Gen_Info(s,rt,d+1);

			size[rt]+=size[s];

			if (son[rt]==-1||size[s]>size[son[rt]])

				son[rt]=s;

		}

}

void Get_Top(int rt,int tp){

	top[rt]=tp;

	ap[p[rt]=++cnp]=rt;

	if (son[rt]==-1)

		return;

	Get_Top(son[rt],tp);

	for (int i=g.fst[rt];i;i=g.nxt[i]){

		int s=g.y[i];

		if (s!=fa[rt]&&s!=son[rt])

			Get_Top(s,s);

	}

}

int find(int x){

	return lower_bound(Ha+1,Ha+hs+1,x)-Ha;

}

void build(int &rt,int L,int R){

	rt=++tot;

	if (L==R){

		ls[rt]=rs[rt]=0;

		return;

	}

	int mid=(L+R)>>1;

	build(ls[rt],L,mid);

	build(rs[rt],mid+1,R);

}

void access(int prt,int &rt,int L,int R,int pos){

	if (!rt||rt==prt)

		rt=++tot;

	Next[prt]=rt;

	if (L==R)

		return;

	int mid=(L+R)>>1;

	if (pos<=mid){

		access(ls[prt],ls[rt],L,mid,pos);

		if (!rs[rt])

			rs[rt]=rs[prt];

	}

	else {

		access(rs[prt],rs[rt],mid+1,R,pos);

		if (!ls[rt])

			ls[rt]=ls[prt];

	}

}

void build_pp(int rt){

	if (!rt)

		return;

	for (int i=rt;i;i=Next[i])

		app[pp[i]=++tpp]=i;

	build_pp(ls[rt]);

	build_pp(rs[rt]);

}

int lowbit(int x){

	return x&-x;

}

void add(int x,int d){

	for (;x<=tpp;x+=lowbit(x))

		sum[x]+=d;

}

int Sum(int x){

	int ans=0;

	for (;x>0;x-=lowbit(x))

		ans+=sum[x];

	return ans;

}

void update(int rt,int L,int R,int pos,int v){

	add(pp[rt],v);

	if (L==R)

		return;

	int mid=(L+R)>>1;

	if (pos<=mid)

		update(ls[rt],L,mid,pos,v);

	else

		update(rs[rt],mid+1,R,pos,v);

}

int query(int prt,int rt,int L,int R,int pos){

	if (R<pos)

		return 0;

	if (L>=pos)

		return Sum(pp[rt])-Sum(pp[prt]);

	int mid=(L+R)>>1;

	return query(ls[prt],ls[rt],L,mid,pos)+query(rs[prt],rs[rt],mid+1,R,pos);

}

int Tquery(int a,int b,int pos){

	int f1=top[a],f2=top[b];

	int total=0;

	while (f1!=f2){

		if (depth[f1]<depth[f2])

			swap(f1,f2),swap(a,b);

		total+=query(root[p[f1]-1],root[p[a]],1,hs,pos);

		a=fa[f1],f1=top[a];

	}

	if (depth[a]>depth[b])

		swap(a,b);

	total+=query(root[p[a]-1],root[p[b]],1,hs,pos);

	return total;

}

int main(){

	scanf("%d%d",&n,&Q);

	for (int i=1;i<=n;i++)

		scanf("%d",&v[i]),Ha[i]=v[i];

	hs=n;

	g.clear();

	for (int i=1,a,b;i<n;i++){

		scanf("%d%d",&a,&b);

		g.add(a,b);

		g.add(b,a);

	}

	for (int i=1;i<=Q;i++){

		scanf("%d%d%d",&q[i].k,&q[i].a,&q[i].b);

		if (q[i].k==0)

			Ha[++hs]=q[i].b;

	}

	LSH();

	Get_Gen_Info(1,0,0);

	Get_Top(1,1);

	for (int i=1;i<=n;i++)

		val[i].clear();

	for (int i=1;i<=n;i++)

		val[p[i]].push_back(find(v[i]));

	for (int i=1;i<=Q;i++)

		if (q[i].k==0)

			val[p[q[i].a]].push_back(find(q[i].b));

	build(root[0],1,hs);

	memset(Next,0,sizeof Next);

	for (int i=1;i<=n;i++)

		for (int j=0;j<val[i].size();j++)

			access(root[i-1],root[i],1,hs,val[i][j]);

	build_pp(root[0]);

	memset(sum,0,sizeof sum);

	for (int i=1;i<=n;i++)

		update(root[p[i]],1,hs,find(v[i]),1);

	for (int i=1;i<=Q;i++){

		if (q[i].k==0){

			update(root[p[q[i].a]],1,hs,find(v[q[i].a]),-1);

			update(root[p[q[i].a]],1,hs,find(v[q[i].a]=q[i].b),1);

		}

		else {

			int L=1,R=hs,mid,ans=-1;

			while (L<=R){

				mid=(L+R)>>1;

				if (Tquery(q[i].a,q[i].b,mid)>=q[i].k)

					L=mid+1,ans=mid;

				else

					R=mid-1;

			}

			if (!~ans)

				puts("invalid request!");

			else

				printf("%d\n",Ha[ans]);

		}

	}

	return 0;

}