Problem: In Homer's country, there are n cities numbered 1 to n and they form a tree. That is, there are (n-1) undirected roads between these n cities and every two cities can reach each other through these roads. 

Homer's country is an industrial country, and each of the n cities in it contains some mineral resource. The mineral resource of city i is labeled a_i. 

Homer is given the plans of the country in the following q years. The plan of the i-th year is described by four parameters u_i, v_i, l_i and r_i, and he is asked to find any mineral resource c_i such that the following two conditions hold: 

  * mineral resource c_i appears an odd number of times between city u_i and city v_i; and 
  * l_i ≤ c_i ≤ r_i. 



As the best friend of Homer, he asks you for help. For every plan, find any such mineral resource c_i, or tell him that there doesn't exist one.

Input

The first line contains two integers n (1 ≤ n ≤ 3 ⋅ 10^5) and q (1 ≤ q ≤ 3 ⋅ 10^5), indicating the number of cities and the number of plans.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Then the i-th line of the following (n-1) lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n) with x_i ≠ y_i, indicating that there is a bidirectional road between city x_i and city y_i. It is guaranteed that the given roads form a tree.

Then the i-th line of the following q lines contains four integers u_i, v_i, l_i, r_i (1 ≤ u_i ≤ n, 1 ≤ v_i ≤ n, 1 ≤ l_i ≤ r_i ≤ n), indicating the plan of the i-th year.

Output

Print q lines, the i-th of which contains an integer c_i such that 

  * c_i = {-1} if there is no such mineral resource that meets the required condition; or 
  * c_i is the label of the chosen mineral resource of the i-th year. The chosen mineral resource c_i should meet those conditions in the i-th year described above in the problem statement. If there are multiple choices of c_i, you can print any of them. 

Example

Input


6 8
3 2 1 3 1 3
1 2
1 3
2 4
2 5
4 6
3 5 1 1
3 5 1 3
3 5 1 3
1 1 2 2
1 1 3 3
1 4 1 5
1 6 1 3
1 6 1 3


Output


-1
2
3
-1
3
2
2
3

Note

In the first three queries, there are four cities between city 3 and city 5, which are city 1, city 2, city 3 and city 5. The mineral resources appear in them are mineral resources 1 (appears in city 3 and city 5), 2 (appears in city 2) and 3 (appears in city 1). It is noted that 

  * The first query is only to check whether mineral source 1 appears an odd number of times between city 3 and city 5. The answer is no, because mineral source 1 appears twice (an even number of times) between city 3 and city 5. 
  * The second and the third queries are the same but they can choose different mineral resources. Both mineral resources 2 and 3 are available. 

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int bs=775,BS=548;
struct query
{
	int l,r,nl,nr,id,adid;
	bool adtg;
}Q[300010],nQ[300010];
vector<int>g[300010];
int a[300010],dep[300010],fa[300010][20],st[300010],ed[300010],dfn[600010],ans[300010],ck[550][550],h[550],cnt;
bool fl[300010],in[300010];
inline int read()
{
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')
		c=getchar();
	while(c>='0'&&c<='9')
	{
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x;
}
inline void write(int x)
{
	if(!x)
	{
		puts("-1");
		return;
	}
	int sta[10],tp=0;
	while(x)
	{
		sta[++tp]=x%10;
		x/=10;
	}
	while(tp)
		putchar(sta[tp--]+'0');
	putchar('\n');
}
bool cmp(query x,query y)
{
	if(x.l/bs!=y.l/bs)
		return x.l<y.l;
	if((x.l/bs)&1)
		return x.r<y.r;
	return x.r>y.r;
}
void dfs(int x,int f)
{
	dep[x]=dep[f]+1;
	fa[x][0]=f;
	st[x]=++cnt;
	dfn[cnt]=x;
	for(int i=1;i<20;i++)
		fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=0;i<g[x].size();i++)
		if(g[x][i]!=f)
			dfs(g[x][i],x);
	ed[x]=++cnt;
	dfn[cnt]=x;
}
inline int LCA(int u,int v)
{
	for(int i=19;~i;i--)
		if(((dep[u]-dep[v])>>i)&1)
			u=fa[u][i];
	if(u==v)
		return u;
	for(int i=19;~i;i--)
		if(fa[u][i]!=fa[v][i])
		{
			u=fa[u][i];
			v=fa[v][i];
		}
	return fa[u][0];
}
inline void add(int x)
{
	if(fl[x])
		fl[x]=false;
	else
	{
		fl[x]=true;
		if(!in[x])
		{
			int bl=x/BS;
			ck[bl][++h[bl]]=x;
			in[x]=true;
		}
	}
}
int main()
{
	int n=read(),q=read(),i,j,x,y,L=1,R=0,lca;
	for(i=1;i<=n;i++)
		a[i]=read()-1;
	for(i=1;i<n;i++)
	{
		x=read();
		y=read();
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,1);
	for(i=1;i<=q;i++)
	{
		Q[i].l=read();
		Q[i].r=read();
		Q[i].nl=read()-1;
		Q[i].nr=read()-1;
		if(dep[Q[i].l]>dep[Q[i].r])
			swap(Q[i].l,Q[i].r);
		lca=LCA(Q[i].r,Q[i].l);
		if(lca==Q[i].l)
		{
			Q[i].adtg=false;
			Q[i].l=st[Q[i].l];
			Q[i].r=st[Q[i].r];
		}
		else
		{
			if(st[Q[i].l]<st[Q[i].r])
			{
				Q[i].l=ed[Q[i].l];
				Q[i].r=st[Q[i].r];
			}
			else
			{
				int tmp=Q[i].l;
				Q[i].l=ed[Q[i].r];
				Q[i].r=st[tmp];
			}
			Q[i].adtg=true;
			Q[i].adid=a[lca];
		}
		Q[i].id=i;
	}
	sort(Q+1,Q+q+1,cmp);
	for(i=1;i<=q;i++)
	{
		while(R<Q[i].r)
			add(a[dfn[++R]]);
		while(R>Q[i].r)
			add(a[dfn[R--]]);
		while(L>Q[i].l)
			add(a[dfn[--L]]);
		while(L<Q[i].l)
			add(a[dfn[L++]]);
		if(Q[i].adtg)
			add(Q[i].adid);
		x=Q[i].nl;
		y=Q[i].nr;
		int bx=x/BS,by=y/BS;
		if(bx==by)
		{
			for(j=x;j<=y;j++)
				if(fl[j])
					break;
			if(j>y)
				ans[Q[i].id]=-1;
			else
				ans[Q[i].id]=j;
		}
		else
		{
			for(j=x;j<(bx+1)*BS;j++)
				if(fl[j])
					break;
			if(j<(bx+1)*BS)
			{
				ans[Q[i].id]=j;
				if(Q[i].adtg)
					add(Q[i].adid);
				continue;
			}
			for(j=by*BS;j<=y;j++)
				if(fl[j])
					break;
			if(j<=y)
			{
				ans[Q[i].id]=j;
				if(Q[i].adtg)
					add(Q[i].adid);
				continue;
			}
			for(j=bx+1;j<by;j++)
			{
				while(h[j]&&!fl[ck[j][h[j]]])
				{
					in[ck[j][h[j]]]=false;
					h[j]--;
				}
				if(h[j])
					break;
			}
			if(j<by)
				ans[Q[i].id]=ck[j][h[j]];
			else
				ans[Q[i].id]=-1;
		}
		if(Q[i].adtg)
			add(Q[i].adid);
	}
	for(i=1;i<=q;i++)
		write(ans[i]+1);
	return 0;
}