别问我为什么拿 剖+线段树+线性基 做这题，理论复杂度 $O(q\log^2(64^2n))$ 开O2 90，不开60

求助好心人卡常，谢谢

#include <cstdio> 
#include <cstring>
#include <iostream>

#define int long long
#define N 100010

int n,m;
int h[N],e[N << 1],ne[N << 1],idx,a[N];
void add_edge(int x,int y)
{
	ne[++idx] = h[x];
	h[x] = idx;
	e[idx] = y;
}

void add(int x,int y)
{
	add_edge(x,y);
	add_edge(y,x);
}
int dfn[N],fdfn[N],dfncnt,top[N],fa[N],sz[N],hson[N],dep[N];
void dfs1(int k,int f,int deep)
{
	sz[k] = 1;
	fa[k] = f;
	dep[k] = deep;
	int maxnum = -1;
	for(int i = h[k];~i;i = ne[i])
	{
		int nx = e[i];
		if(nx == f)
			continue;
		dfs1(nx,k,deep + 1);
		sz[k] += sz[nx];
		if(sz[nx] > maxnum)
		{
			maxnum = sz[nx];
			hson[k] = nx;
		}
	}
}

void dfs2(int k,int tp)
{
	top[k] = tp;
	dfn[k] = ++dfncnt;
	fdfn[dfncnt] = k;
	if(!hson[k])
		return;
	dfs2(hson[k],tp);
	for(int i = h[k];~i;i = ne[i])
	{
		int nx = e[i];
		if(nx == hson[k] || nx == fa[k])
			continue;
		dfs2(nx,nx);
	}
}

struct XXJ
{
	int p[66];
	void init()
	{
		for(int i = 60;~i;i--)
			p[i] = 0;
	}
	void ins(int x)
	{
		if(!x)	return;
		for(int i = 60;~i;i--)
		{
			if(x & (1ll << i))
			{
				if(!p[i])
				{
					p[i] = x;
					break;
				}
				else
					x ^= p[i];
			}
		}
	}
	int query_max()
	{
		int res = 0;
		for(int i = 60;~i;i--)
		{
			if((res ^ p[i]) > res)
				res ^= p[i];
		}
		return res;
	}
	void merge(XXJ B)
	{
		for(int i = 60;~i;i--)
		{
			ins(B.p[i]);
		}
	}
	void cpy(XXJ B)
	{
		for(int i = 60;~i;i--)
			p[i] = B.p[i];
	}
};

struct Tree
{
	int l,r;
	XXJ J;
}tr[N << 2];

#define lson k << 1
#define rson k << 1 | 1

void pushup(int k)
{
	tr[k].J.cpy(tr[lson].J);
	tr[k].J.merge(tr[rson].J);
}

void build(int k,int l,int r)
{
	tr[k].l = l,tr[k].r = r;
	tr[k].J.init();
	if(l == r)
	{
		tr[k].J.ins(a[fdfn[l]]);
		return;
	}
	int mid = l + r >> 1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	pushup(k);
}

XXJ query(int k,int ql,int qr)
{
	int l = tr[k].l,r = tr[k].r;
	if(ql <= l && r <= qr)
		return tr[k].J;
	XXJ res;
	res.init();
	int mid = l + r >> 1;
	if(ql <= mid)
		res.merge(query(lson,ql,qr));
	if(mid < qr)
		res.merge(query(rson,ql,qr));
	return res;
}

XXJ query_way(int x,int y)
{
	XXJ res;
	res.init();
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])
			x ^= y ^= x ^= y;
		res.merge(query(1,dfn[top[x]],dfn[x]));
		x = fa[top[x]];
	}
	if(dfn[x] > dfn[y])
		x ^= y ^= x ^= y;
	res.merge(query(1,dfn[x],dfn[y]));
	return res;
}

inline int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}

signed main()
{
	memset(h,-1,sizeof(h));
	n = read(),m = read();
	for(int i = 1;i <= n;i++)
		a[i] = read();
	
	for(int i = 1,x,y;i < n;i++)
	{
		x = read(),y = read();
		add(x,y);
	}
	dfs1(1,0,1);
	dfs2(1,1);
	build(1,1,n);
	for(int i = 1,x,y;i <= m;i++)
	{
		x = read(),y = read();
		XXJ res = query_way(x,y);
		printf("%lld\n",res.query_max());
	}
	return 0;
}