#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorithm>#define N 8010#define TT 200010#define inf 1000000000using namespace std;inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}//===============================================int n,m;int v[N];int bin[16]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384};//===============================================struct edge{int to,next;}e[2*N];int head[N],cnt;inline void ins(int u,int v){	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;	e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;}//===============================================int l[TT],r[TT],rnd[TT],dat[TT],son[TT],rep[TT],root[4*N];int treesize,wrk;inline void update(int k){son[k]=son[l[k]]+son[r[k]]+rep[k];}inline void right_rotate(int &k){	int t=l[k];	l[k]=r[t];	r[t]=k;	son[t]=son[k];	update(k);	k=t;}inline void left_rotate(int &k){	int t=r[k];	r[k]=l[t];	l[t]=k;	son[t]=son[k];	update(k);	k=t;}inline void insert(int k,int x){	if (!k){k=++treesize;rnd[k]=rand();dat[k]=x;rep[k]=son[k]=1;return;}	son[k]++;	if (x==dat[k]){rep[k]++;return;}	else if (x<dat[k])	{		insert(l[k],x);		if (rnd[l[k]]>rnd[k])right_rotate(k);	}else if (x>dat[k])	{		insert(r[k],x);		if (rnd[r[k]]>rnd[k])left_rotate(k);	}}inline void del(int &k,int x){		if (!k)return;	if (x==dat[k])	{		if (rep[k]>1){rep[k]--;son[k]--;return;}		if (l[k]*r[k]==0)k=l[k]+r[k];		else if (rnd[l[k]]>rnd[r[k]]){right_rotate(k);del(k,x);}		else {left_rotate(k);del(k,x);}	}else if (x<dat[k])del(l[k],x),son[k]--;	else del(r[k],x),son[k]--;}inline void buildtree(int k,int l,int r,int x,int dat){	insert(root[k],dat);	if (l==r)return;	int mid=(l+r)>>1;	if (x<=mid)buildtree(k<<1,l,mid,x,dat);	else buildtree(k<<1|1,mid+1,r,x,dat);}inline void get_rank(int k,int x){	if (!k)return;	if (x==dat[k]){wrk+=son[r[k]];return;}	if (x<dat[k])	{		wrk+=son[r[k]]+rep[k];		get_rank(l[k],x);	}	if (x>dat[k])get_rank(r[k],x);}inline void ask_rank(int k,int l,int r,int x,int y,int d){	if (l==x&&r==y){get_rank(root[k],d);return;}	int mid=(l+r)>>1;	if (y<=mid)ask_rank(k<<1,l,r,x,y,d);	else if (x>mid)ask_rank(k<<1|1,l,r,x,y,d);	else	{		ask_rank(k<<1,l,mid,x,mid,d);		ask_rank(k<<1|1,mid+1,r,mid+1,y,d);	}}inline void change(int k,int l,int r,int x,int s,int t){	del(root[k],s);	insert(root[k],t);	int mid=(l+r)>>1;	if (x<=mid)change(k<<1,l,mid,x,s,t);	else change(k<<1|1,mid+1,r,x,s,t);}//===============================================int place[4*N],pplace[4*N],belong[4*N];int tt;int size[N],fa[N][16],dep[N];bool mrk[N];inline void dfs1(int x,int d){	if (mrk[x])return;mrk[x]=1;	size[x]=1;dep[x]=d;	for (int i=1;i<16;i++)fa[x][i]=fa[fa[x][i-1]][i-1];	for (int i=head[x];i;i=e[i].next)		if (!mrk[e[i].to])		{			fa[e[i].to][0]=x;			dfs1(e[i].to,d+1);			size[x]+=size[e[i].to];		}}inline void dfs2(int x,int chain){	place[x]=++tt;pplace[tt]=x;belong[x]=chain;	int mx=-1,res=-1;	for (int i=head[x];i;i=e[i].next)	if (e[i].to!=fa[x][0])	{		if (size[e[i].to]>mx)		{			mx=size[e[i].to];			res=e[i].to;		}	}	if (res==-1)return;	dfs2(res,chain);	for (int i=head[x];i;i=e[i].next)		if (e[i].to!=res&&e[i].to!=fa[x][0])			dfs2(e[i].to,e[i].to);}inline int LCA(int a,int b){	if (dep[a]<dep[b])swap(a,b);	int des=dep[a]-dep[b];	for (int i=0;i<16;i++)		if (des & (1<<i))a=fa[a][i];	for (int i=15;i>=0;i--)		if (fa[a][i]!=fa[b][i])		{			a=fa[a][i];			b=fa[b][i];		}	if (a==b)return a;	else return b;}inline void calc(int from,int to,int d){	int l,r;	while (belong[from]!=belong[to])	{		l=place[belong[from]];		r=place[from];		ask_rank(1,1,n,l,r,d);	}	if (place[to]+1<=place[from])ask_rank(1,1,n,place[to],place[from],d);}int main(){	srand(1);	n=read();m=read();	for (int i=1;i<=n;i++)v[i]=read();	for (int i=1;i<n;i++)	{		int x=read(),y=read();		ins(x,y);	}	dfs1(1,0);	dfs2(1,1);	for (int i=1;i<=n;i++)buildtree(1,1,n,pplace[i],v[i]);	for (int i=1;i<=m;i++)	{		int k=read(),a=read(),b=read();		if (!k)		{			change(1,1,n,a,v[a],b);			v[a]=b;		}else 		{			int lca=LCA(a,b);			if (dep[lca]-dep[a]+1+dep[lca]-dep[b]+1<k)			{				printf("invalid request!\n");				continue;			}			int L=0,R=inf;			while (L<=R)			{				int md=(L+R)>>1;				wrk=0;//±Èmid´óµÄÊýÓжàÉÙ¸ö 				calc(a,lca,md);				calc(b,lca,md);				if (v[lca]>md)wrk++;				if (wrk<k) R=md-1;				else L=md+1;			}			printf("%d\n",L);		}	}	return 0;}