//#pragma comment(linker, "/STACK:1024000000,1024000000")

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #include<cmath>

 #include<iostream>

 #include<vector>

 typedef long long ll;

 using namespace std;

 const int maxn=;

 const int maxm=;

 int _pow[maxm],m,n;

 int head[maxn],tot;

 int ver[maxn*],depth[maxn*],first[maxn],rmq[maxn*][],id;//5个数组，注意哪个需要乘2

 int pre[maxn],val[maxn];

 inline int read(){

     char k=;char ls;ls=getchar();for(;ls<''||ls>'';k=ls,ls=getchar());

     int x=;for(;ls>=''&&ls<='';ls=getchar())x=(x<<)+(x<<)+ls-'';

     if(k=='-')x=-x;return x;

 }

 struct edge{

     int to,nxt;

 }e[maxn*];//链式前向星建树 

 void init(){

     memset(head,-,sizeof head);

     tot=;

     id=;

 }

 void add_edge(int u,int v){

     e[tot].to=v;

     e[tot].nxt=head[u];

     head[u]=tot++;

 }

 void dfs(int u,int fa,int dep){

     ver[++id]=u;//第i个访问到的结点编号

     depth[id]=dep;//第i个访问到的结点深度

     first[u]=id;

     for(int i=head[u];i!=-;i=e[i].nxt){

         int v=e[i].to;

         if(v==fa) continue;

         pre[v]=u;

         dfs(v,u,dep+);

         ver[++id]=u;//后序遍历，再次访问父节点

         depth[id]=dep;

     }

 }

 void rmq_init(int n){

     int k=int(log(n)/log());

     for(int i=;i<=n;++i)    rmq[i][]=i;

     for(int j=;j<=k;++j){

         for(int i=;i+_pow[j]-<=n;++i){//因为存的是索引

             int a=rmq[i][j-],b=rmq[i+_pow[j-]][j-];

             rmq[i][j]=depth[a]<depth[b]?a:b;

         }

     }

 }

 int rmq_query(int l,int r){

     int k=int(log(r-l+1.0)/log(2.0));

     int a=rmq[l][k],b=rmq[r-_pow[k]+][k];

     return depth[a]<depth[b]?a:b;

 }//返回的依然是索引 

 int LCA(int u,int v){

     int x=first[u],y=first[v];

     if(x>y)swap(x,y);

     int res=rmq_query(x,y);

     return ver[res];

 }

 vector<int>path;

 //int path[maxn];

 void solve(int k,int a,int b){

     //int cnt=0;

     path.clear();

     int lca=LCA(a,b);

     while(b!=lca) path.push_back(val[b]),b=pre[b];

     while(a!=lca) path.push_back(val[a]),a=pre[a];

     path.push_back(val[lca]);

     if(path.size()<k){

         printf("invalid request!\n");

         return;

     }

     sort(path.begin(),path.end(),greater<int>());

     printf("%d\n",path[k-]);

     return;

 }

 int main(){

     for(int i=;i<maxm;++i)    _pow[i]=<<i; //预处理2^n

     int k,a,b;

     n=read();m=read();

     init();

     for(int i=;i<=n;i++) val[i]=read();

     for(int i=;i<n-;++i){

         a=read(),b=read();

         add_edge(a,b);

         add_edge(b,a);

     }

     dfs(,-,);

     rmq_init(*n-);

     for(int i=;i<m;++i){

         k=read();a=read();b=read();

         if(k) solve(k,a,b);

         else val[a]=b;

     }

     return ;

 }