#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
inline void read(int &x){char ch = getchar();char c = ch;x = 0;while(ch < ‘0‘ || ch > ‘9‘)c = ch, ch = getchar();while(ch <= ‘9‘ && ch >= ‘0‘)x = x * 10 + ch - ‘0‘, ch = getchar();if(c == ‘-‘)x = -x;}
inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;}

const int MAXN = 80000 + 10;

struct Edge{int u,v,next;}edge[MAXN << 1];
int head[MAXN],cnt,n,m,w[MAXN],p[20][MAXN],deep[MAXN],fa[MAXN],num[MAXN],b[MAXN];
inline void insert(int a,int b){edge[++cnt] = Edge{a, b, head[a]},head[a] = cnt;}

int llog2[MAXN],pow2[30];

void dfs(int u)
{
	for(int pos = head[u];pos;pos = edge[pos].next)
	{
		int v = edge[pos].v;
		if(b[v])continue;
		b[v] = true,deep[v] = deep[u] + 1,p[0][v] = u,fa[v] = u,dfs(v);
	}
}

inline void yuchuli()
{
	b[1] = true,deep[1] = 0,dfs(1);
	register int i;
	for(i = 1;i <= llog2[n];i ++)
		for(int j = n;j >= 1;j --)
			p[i][j] = p[i - 1][p[i - 1][j]];
}

inline int lca(int va, int vb)
{
	register int i;
	if(deep[va] < deep[vb])swap(va, vb);
	for(i = llog2[n];i >= 0;i --)
		if(deep[va] - pow2[i] >= deep[vb])
			va = p[i][va];
	if(va == vb)return va;
	for(i = llog2[n];i >= 0;i --)
		if(p[i][va] != p[i][vb])
			va = p[i][va],vb = p[i][vb];
	return p[0][va];
}

int ans[MAXN],rank;

inline void work(int s, int t, int k)
{
	int anc = lca(s, t);
	int now = s;
	register int i = 1;
	num[i] = w[now];
	while(now != anc)
		num[++i] = w[(now = fa[now])];
	now = t;
	while(now != anc)
		num[++i] = w[now], now = fa[now];
	std::sort(num + 1, num + 1 + i);
	if(i >= k)
		ans[++rank] = num[i - k + 1];
	else rank++;
}

int main()
{
	register int i,tmp1,tmp2,tmp3;
	llog2[0] = -1,pow2[0] = 1;
	for(int i = 1;i <= MAXN;i ++)llog2[i] = llog2[i >> 1] + 1;
	for(int i = 1;i <= 25; i++)pow2[i] = (pow2[i - 1] << 1);
	read(n),read(m);
	for(i = 1;i <= n;i ++)read(w[i]);
	for(i = 1;i < n;i ++)read(tmp1),read(tmp2),insert(tmp1, tmp2),insert(tmp2, tmp1);
	yuchuli();
	for(i = 1;i <= m;i ++)
	{
		read(tmp1),read(tmp2),read(tmp3);
		if(tmp1)work(tmp2, tmp3, tmp1);
		else w[tmp2] = tmp3;
	}
	for(int i = 1;i < rank;i ++)
		if(ans[i])
			printf("%d\n", ans[i]);
		else
			printf("invalid request!\n"); 
	if(ans[rank])
		printf("%d\n", ans[rank]);
	else
		printf("invalid request!\n"); 
	return 0;
}