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:
  //#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define ll long long
//#define file
using namespace std;

int c[300001],C[300001],n,Q,i,j,k,l,L,R,Mid,S,s,x,y,l1,r1,Lca;
int a[600001][2],ls[300001],len;
int nx[300001],top[300001],sz[300001],d[300001],fa[300001],bg[300001],ed[300001];
int tr[20000001][3];
char st[16800001];
int I=-1;
vector<int> v[300001];

ll random(ll x,ll y) {return (32768ll*rand()+rand())%(y-x+1)+x;}
void NEW(int x,int y) {++len;a[len][0]=y;a[len][1]=ls[x];ls[x]=len;}

char ch;
int Read()
{
	int x=0;
	++I;
	while (st[I]<'0' || st[I]>'9') ++I;
	while (st[I]>='0' && st[I]<='9') x=x*10+(st[I]-'0'),++I;
	return x;
}
void Write(int x)
{
	static char st[21];
	int i=0;
	while (x) st[++i]=x%10+'0',x/=10;
	while (i) putchar(st[i--]);
	putchar('\n');
	return;
}
void copy(int t1,int t2) {memcpy(tr[t1],tr[t2],sizeof(tr[t1]));}
void New(int t,int x) {++len;copy(len,tr[t][x]);tr[t][x]=len;}
void dfs(int Fa,int t)
{
	int i,mx=-1;
	d[t]=d[Fa]+1;bg[t]=++j,sz[t]=1;fa[t]=Fa;
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa)
	{
		dfs(t,a[i][0]);
		sz[t]+=sz[a[i][0]];
		if (sz[a[i][0]]>mx) mx=sz[a[i][0]],nx[t]=a[i][0];
	}
	ed[t]=j;
}
void Dfs(int Fa,int t)
{
	int i;
	if (nx[t]) top[nx[t]]=top[t],Dfs(t,nx[t]);
	
	for (i=ls[t]; i; i=a[i][1])
	if (a[i][0]!=Fa && a[i][0]!=nx[t])
	{
		top[a[i][0]]=a[i][0];
		Dfs(t,a[i][0]);
	}
}
int lca(int x,int y)
{
	int i;
	while (x!=y)
	{
		if (bg[x]<=bg[y] && ed[y]<=ed[x]) return x;
		if (bg[y]<=bg[x] && ed[x]<=ed[y]) return y;
		if (d[top[x]]>d[top[y]]) x=fa[top[x]];
		else y=fa[top[y]];
	}
	return x;
}

void change(int t,int l,int r,int x,int y,int s)
{
	int mid=(l+r)/2;
	if (x<=l && r<=y) {tr[t][2]^=s;return;}
	if (x<=mid) New(t,0),change(tr[t][0],l,mid,x,y,s);
	if (mid<y) New(t,1),change(tr[t][1],mid+1,r,x,y,s);
}
int find(int t,int l,int r,int x)
{
	int mid=(l+r)/2,ans=0;
	if (!t) return 0;
	if (l==r) return tr[t][2];
	
	if (x<=mid) ans=find(tr[t][0],l,mid,x);
	else ans=find(tr[t][1],mid+1,r,x);
	return ans^tr[t][2];
}

void init()
{
	j=0,dfs(0,1);
	Dfs(0,1);
	len=n;
	fo(i,1,n) v[c[i]].push_back(i);
	fo(i,1,n)
	{
		l=v[i].size(),copy(i,i-1);
		fo(j,0,l-1)
		k=v[i][j],change(i,1,n,bg[k],ed[k],C[i]);
	}
}

int main()
{
	srand(time(NULL));
	#ifdef file
	freopen("CF1479D.in","r",stdin);
	freopen("CF1479D.out","w",stdout);
	#endif
	
	fread(st,1,16800001,stdin);
	n=Read(),Q=Read();
	fo(i,1,n) c[i]=Read();
	fo(i,1,n) C[i]=random(0,2147483647);
	fo(i,1,n-1) j=Read(),k=Read(),NEW(j,k),NEW(k,j);
	init();
	
	for (;Q;--Q)
	{
		x=Read(),y=Read(),l1=Read(),r1=Read(),Lca=lca(x,y);
		if (l1>1) S=find(l1-1,1,n,bg[x])^find(l1-1,1,n,bg[y]); else S=0;
		s=find(r1,1,n,bg[x])^find(r1,1,n,bg[y]);
		if (l1<=c[Lca] && r1>=c[Lca]) s^=C[c[Lca]];
		
		if (s==S) printf("-1\n");
		else
		{
			L=l1,R=r1;
			while (L<R)
			{
				Mid=(L+R)/2,s=find(Mid,1,n,bg[x])^find(Mid,1,n,bg[y]);
				if (l1<=c[Lca] && Mid>=c[Lca]) s^=C[c[Lca]];
				if (s==S) L=Mid+1; else R=Mid;
			}
			Write(L);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}