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 LL long long
#define pa pair<int,int>
const int Maxn=300010;
const int inf=2147483647;
const double pi=acos(-1.0);
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
//LL Rand(){return(LL)rand()*rand()*rand()*rand();}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int n,q,a[Maxn],root[Maxn],lc[Maxn*20],rc[Maxn*20],tot=0,fa[Maxn][19],dep[Maxn];
LL v[Maxn],c[Maxn*20];
vector<int>G[Maxn];
void insert(int&u,int l,int r,int p,LL x)
{
	if(!u)u=++tot;
	c[u]^=x;
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)insert(lc[u],l,mid,p,x);
	else insert(rc[u],mid+1,r,p,x);
}
void merge(int&u1,int u2)
{
	if(!u1){u1=u2;return;}
	if(!u2)return;
	c[u1]^=c[u2];
	merge(lc[u1],lc[u2]),merge(rc[u1],rc[u2]);
}
void dfs(int x,int f)
{
	dep[x]=dep[f]+1;fa[x][0]=f;
	for(int i=1;(1<<i)<=dep[x];i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	insert(root[x],1,n,a[x],v[a[x]]);
	if(f)merge(root[x],root[f]);
	for(int i=0;i<G[x].size();i++)
	{
		int y=G[x][i];
		if(y==f)continue;
		dfs(y,x);
	}
}
int LCA(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int i=18;i>=0;i--)if((1<<i)<=dep[x]-dep[y])x=fa[x][i];
	if(x==y)return x;
	for(int i=18;i>=0;i--)
	if((1<<i)<=dep[x]&&fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int Query(int rt1,int rt2,int l,int r,int x)
{
	if(l==r)
	{
		LL t=(c[rt1]^c[rt2]);
		if(x==l)t^=v[x];
		if(t)return l;
		return -1;
	}
	int mid=l+r>>1;
	LL t=(c[lc[rt1]]^c[lc[rt2]]);
	if(l<=x&&x<=mid)t^=v[x];
	if(t)return Query(lc[rt1],lc[rt2],l,mid,x);
	return Query(rc[rt1],rc[rt2],mid+1,r,x);
}
int query(int rt1,int rt2,int l,int r,int ql,int qr,int x)
{
	if(ql==l&&qr==r)return Query(rt1,rt2,l,r,x);
	int mid=l+r>>1;
	if(qr<=mid)return query(lc[rt1],lc[rt2],l,mid,ql,qr,x);
	if(ql>mid)return query(rc[rt1],rc[rt2],mid+1,r,ql,qr,x);
	int t=query(lc[rt1],lc[rt2],l,mid,ql,mid,x);
	if(t!=-1)return t;
	return query(rc[rt1],rc[rt2],mid+1,r,mid+1,qr,x);
}
int main()
{
//	srand(200815147);
	n=read(),q=read();
	for(int i=1;i<=n;i++)a[i]=read(),v[i]=rd();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		G[x].push_back(y),G[y].push_back(x);
	}
	dep[0]=-1;dfs(1,0);
	while(q--)
	{
		int u=read(),v=read(),w=LCA(u,v),l=read(),r=read();
		printf("%d\n",query(root[u],root[v],1,n,l,r,a[w]));
	}
}