Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,q;

#define MAXN 100010

int val[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct PersistentTrie

{

	struct node

	{

		int c[2],s[2];

	}t[MAXN * 32];

	int ptr;

	PersistentTrie(){ptr = 0;}

	int newnode(){return ++ptr;}

	int root[MAXN];

	void insert(int rt,int fa,int v)

	{

		root[rt] = newnode();rt = root[rt];

		t[rt] = t[root[fa]];

		for(int i = 30;i >= 0;--i)

		{

			int w = (v >> i) & 1;

			int k = newnode();t[k] = t[t[rt].c[w]];t[rt].c[w] = k;

			++t[rt].s[w];

			rt = t[rt].c[w];

		}

		return;

	}

	int query(int l,int r,int k)

	{

		int rtr = root[r],rtl = root[l];

		int res = 0;

		for(int i = 30;i >= 0;--i)

		{

			int w = (k >> i) & 1;

			if(t[rtr].s[w ^ 1] - t[rtl].s[w ^ 1] != 0)

			{

				rtr = t[rtr].c[w ^ 1];

				rtl = t[rtl].c[w ^ 1];

				res |= 1 << i;

			}

			else

			{

				rtr = t[rtr].c[w];

				rtl = t[rtl].c[w];

			}

		}

		return res;

	}

}t1,t2;

int fa[MAXN],siz[MAXN],top[MAXN],dep[MAXN],son[MAXN];

int rnk[MAXN],th[MAXN],tot = 0;

void dfs1(int k,int depth)

{

	siz[k] = 1;dep[k] = depth;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	rnk[k] = ++tot;th[tot] = k;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

void dfs(int k)

{

	t1.insert(k,fa[k],val[k]);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			dfs(e[i].to);

		}

	}

	return;

}

int main()

{

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

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

	{

		scanf("%d",&val[i]);

	}

	int a,b;

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

	{

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

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

	dfs(1);

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

	{

		t2.insert(i,i - 1,val[th[i]]);

	}

	int opt,x,y,v;

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

	{

		scanf("%d",&opt);

		if(opt == 1)

		{

			scanf("%d%d",&x,&v);

			printf("%d\n",t2.query(rnk[x] - 1,rnk[x] + siz[x] - 1,v));

		}

		else

		{

			scanf("%d%d%d",&x,&y,&v);

			int lca = LCA(x,y);

			int ans = max(t1.query(fa[lca],x,v),t1.query(fa[lca],y,v));

			printf("%d\n",ans);

		}

	}

	return 0;

}