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;
#define mp make_pair
#define pb push_back
#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x,T y){x<y?x=y:T();}
template <typename T> void chkmin(T &x,T y){y<x?x=y:T();}
template <typename T> void readint(T &x)
{
	x=0;int f=1;char c;
	for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=x*10+(c-'0');
	x*=f;
}
const int MOD1=1010101039,MOD2=1000020001;
const int MAXN=300005,MAXK=19,MAXV=MAXN*21;

int n,a[MAXN];
vector<int> G[MAXN];
int anc[MAXN][MAXK],dep[MAXN];
int stot,vs[MAXN];
pii h[MAXV],pw[MAXN];
int lch[MAXV],rch[MAXV];
pii operator *(pii a,pii b){return mp(1ll*a.x*b.x%MOD1,1ll*a.y*b.y%MOD2);}
pii operator +(pii a,pii b){return mp((a.x+b.x)%MOD1,(a.y+b.y)%MOD2);}
int modify(int id,int l,int r,int x)
{
	int rt=++stot;
	if(l==r)
	{
		h[rt]=mp(1-h[id].x,1-h[id].y);
		return rt;
	}
	int mid=(l+r)>>1;
	if(x<=mid)lch[rt]=modify(lch[id],l,mid,x),rch[rt]=rch[id];
	else rch[rt]=modify(rch[id],mid+1,r,x),lch[rt]=lch[id];
	h[rt]=h[lch[rt]]*pw[r-mid]+h[rch[rt]];
	return rt;
}
int query(int u,int v,int l,int r,int ql,int qr)
{
	if(h[u]==h[v])return -1;
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(qr<=mid)return query(lch[u],lch[v],l,mid,ql,qr);
	if(ql>mid)return query(rch[u],rch[v],mid+1,r,ql,qr);
	int s=query(lch[u],lch[v],l,mid,ql,mid);
	if(s>0)return s;
	return query(rch[u],rch[v],mid+1,r,mid+1,qr);
}
void dfs(int u,int pa)
{
	for(int j=1;j<MAXK;++j)anc[u][j]=anc[anc[u][j-1]][j-1];
	for(auto v:G[u])
		if(v!=pa)
		{
			anc[v][0]=u;
			dep[v]=dep[u]+1;
			vs[v]=modify(vs[u],1,n,a[v]);
			dfs(v,u);
		}
}
int lca(int u,int v)
{
	if(dep[u]>dep[v])swap(u,v);
	for(int i=MAXK-1;i>=0;--i)if(dep[anc[v][i]]>=dep[u])v=anc[v][i];
	if(u==v)return u;
	for(int i=MAXK-1;i>=0;--i)if(anc[u][i]!=anc[v][i])u=anc[u][i],v=anc[v][i];
	return anc[u][0];
}

int main()
{
	#ifdef LOCAL
	freopen("code.in","r",stdin);
//	freopen("code.out","w",stdout);
	#endif
	int Q,u,v,l,r;
	readint(n),readint(Q);
	for(int i=1;i<=n;++i)readint(a[i]);
	for(int i=1;i<n;++i)readint(u),readint(v),G[u].pb(v),G[v].pb(u);
	pw[0]=mp(1,1);pw[1]=mp(29,101);
	for(int i=2;i<=n;++i)pw[i]=pw[i-1]*pw[1]; 
	vs[1]=modify(0,1,n,a[1]);
	dep[1]=1;
	dfs(1,-1);
	while(Q--)
	{
		readint(u),readint(v),readint(l),readint(r);
		int d=lca(u,v);
		if(a[d]<l || a[d]>r)
		{
			int t=query(vs[u],vs[v],1,n,l,r);
			printf("%d\n",t);
		}
		else
		{
			int t=(a[d]==l?-1:query(vs[u],vs[v],1,n,l,a[d]-1));
			if(t<0)
			{
				t=(a[d]==r?-1:query(vs[u],vs[v],1,n,a[d]+1,r));
				if(t<0)
				{
					t=query(vs[u],vs[v],1,n,a[d],a[d]);
					if(t==-1)t=a[d];
					else t=-1;
				}
			}
			printf("%d\n",t);
		}
	}
	return 0;
}