rt，可持久化01trie，全WA。。。

#include <bits/stdc++.h>
using namespace std;
struct aaaa{
	int ls,rs,sum;
}t[100010*35],t2[100010*35];
int f[100010][30],d[100010],dfn[100010],low[100010],tme,n,m,a[100010],cnt,cnt2,rt[100010],rt2[100010];
vector<int>v[100010];
inline int add(int p,int u,int d){
	int k=++cnt;
	t[k]=t[p];
	t[k].sum++;
	if(u==-1)return k;
	int o=((d>>u)&1);
	if(o==0)t[k].ls=add(t[k].ls,u-1,d);
	else t[k].rs=add(t[k].rs,u-1,d);
	return k;
}
inline int add2(int p,int u,int d){
	int k=++cnt2;
	t2[k]=t2[p];
	t2[k].sum++;
	if(u==-1)return k;
	int o=((d>>u)&1);
	if(o==0)t2[k].ls=add2(t2[k].ls,u-1,d);
	else t2[k].rs=add2(t2[k].rs,u-1,d);
	return k;
}
inline int query(int r,int l,int u,int d){
	if(u==-1)return 0;
	int o=(((d>>u)&1)^1);
	if(o==0){
		if(t[t[r].ls].sum-t[t[l].ls].sum>0){
			return query(t[r].ls,t[l].ls,u-1,d)+(1ll<<u);
		}
		else return query(t[r].rs,t[l].rs,u-1,d);
	}
	else{
		if(t[t[r].rs].sum-t[t[l].rs].sum>0){
			return query(t[r].rs,t[l].rs,u-1,d)+(1ll<<u);
		}
		else return query(t[r].ls,t[l].ls,u-1,d);
	}
}
inline int query2(int r,int l,int u,int d){
	if(u==-1)return 0;
	int o=(((d>>u)&1)^1);
	if(o==0){
		if(t2[t2[r].ls].sum-t2[t2[l].ls].sum>0){
			return query2(t2[r].ls,t2[l].ls,u-1,d)+(1ll<<u);
		}
		else return query2(t2[r].rs,t2[l].rs,u-1,d);
	}
	else{
		if(t2[t2[r].rs].sum-t2[t2[l].rs].sum>0){
			return query2(t2[r].rs,t2[l].rs,u-1,d)+(1ll<<u);
		}
		else return query2(t2[r].ls,t2[l].ls,u-1,d);
	}
}
inline void dfs(int sx,int fa){
	dfn[sx]=++tme;
	f[sx][0]=fa;
	d[sx]=d[fa]+1;
	rt[dfn[sx]]=add(rt[dfn[sx]-1],30,a[sx]);
	rt2[sx]=add2(rt2[fa],30,a[sx]);
	for(int x=1;(1<<x)<=d[sx];x++){
		f[sx][x]=f[f[sx][x-1]][x-1];
	}
	for(int x=0;x<v[sx].size();x++){
		if(v[sx][x]==fa)continue;
		dfs(v[sx][x],sx);
	}
	low[sx]=tme;
}
inline int lca(int sx,int sy){
	if(d[sx]<d[sy])swap(sx,sy);
	for(int x=29;x>=0;x--){
		if(d[f[sx][x]]<=d[sy])continue;
		sx=f[sx][x];
	}
	if(f[sx][0]==f[sy][0])return f[sx][0];
	for(int x=29;x>=0;x--){
		if(f[sx][x]==f[sy][x])continue;
		sx=f[sx][x],sy=f[sy][x];
	}
	return f[sx][0];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int x=1;x<=n;x++){
		cin>>a[x];
	}
	for(int x=1;x<n;x++){
		int u,w;
		cin>>w>>u;
		v[u].push_back(w);
		v[w].push_back(u);
	}
	dfs(1,0);
	while(m--){
		int op,x,y,z;
		cin>>op;
		if(op==1){
			cin>>x>>z;
			cout<<query(rt[low[x]],rt[dfn[x]-1],30,z)<<endl;
		}
		else{
			cin>>x>>y>>z;
			cout<<max(query2(rt2[x],rt2[f[lca(x,y)][0]],30,z),query2(rt2[y],rt2[f[lca(x,y)][0]],30,z))<<endl;
		}
	}
}