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("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
int rd(){
	int x;
	scanf("%d",&x);
	return x;
}
#else
int p1=5000000;
char buf[5000005];
int gc(){
	if(p1>=5000000)fread(buf,1,5000000,stdin),p1=0;
	return buf[p1++];
}
int rd(){
	int x=0;
	char ch=gc();
	while(ch<'0'||ch>'9')ch=gc();
	while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=gc();
	return x;
}
#endif
int n,Q,h[300005],s[300005],onp[300005],cnt,a[300005],bel[600005];
int sign,nowt,p[300005][20],d[300005],bel2[300005],cntb[300005],ccnt[300005];
int S[300005],E[300005],st[300005],blk,ans[300005],ed[300005],id[600005];
struct Edge{
	int to,next;
}e[600005];
struct Query{
	int tp,l,r,x,y,id;
}q[300005];
inline bool operator <(Query a,Query b){
	if(bel[a.x]!=bel[b.x])return bel[a.x]<bel[b.x];
	return bel[a.x]&1?a.y<b.y:a.y>b.y;
}
void Add_Edge(int x,int y){
	e[++cnt].to=y,e[cnt].next=h[x],h[x]=cnt;
}
void DFS(int now,int fa,int depth){
	p[now][0]=fa,d[now]=depth,st[now]=++sign,id[st[now]]=now;
	for(int i=1;i<=18;i++)p[now][i]=p[p[now][i-1]][i-1];
	for(int i=h[now];i;i=e[i].next){
		int y=e[i].to;
		if(y==fa)continue;
		DFS(y,now,depth+1);
	}
	ed[now]=++sign,id[ed[now]]=now;
}
int LCA(int x,int y){
	if(d[x]<d[y])swap(x,y);
	for(int i=18;i>=0;i--)if(d[p[x][i]]>=d[y])x=p[x][i];
	if(x==y)return x;
	for(int i=18;i>=0;i--)if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];
	return p[x][0];
}
int Que(int l,int r){
	if(bel2[l]==bel2[r]){
		for(int j=l;j<=r;j++)if(ccnt[j]%2==1)return j;
		return -1;
	}
	for(int i=bel2[l]+1;i<bel2[r];i++){
		if(!cntb[i])continue;
		for(int j=S[i];j<=E[i];j++)if(ccnt[j]%2==1)return j;
	}
	for(int j=l;j<=E[bel2[l]];j++)if(ccnt[j]%2==1)return j;
	for(int j=S[bel2[r]];j<=r;j++)if(ccnt[j]%2==1)return j;
	return -1;
}
inline void Rev(int x){
	if(!onp[x]){
		onp[x]=1,ccnt[a[x]]++;
		if(ccnt[a[x]]%2==1)cntb[bel2[a[x]]]++;
		else cntb[bel2[a[x]]]--;
	}
	else {
		onp[x]=0,ccnt[a[x]]--;
		if(ccnt[a[x]]%2==1)cntb[bel2[a[x]]]++;
		else cntb[bel2[a[x]]]--;
	}
}
int main(){
	n=rd(),Q=rd(),blk=pow(n,0.5);
	for(int i=1;i<=n;i++)a[i]=rd(),bel2[i]=i/blk+1,E[bel2[i]]=i;
	for(int i=n;i;i--)S[bel2[i]]=i;
	for(int i=1,x,y;i<n;i++)x=rd(),y=rd(),Add_Edge(x,y),Add_Edge(y,x);
	DFS(1,0,1);
	for(int i=1;i<=sign;i++)bel[i]=i/blk+1;
	for(int i=1,x,y,l,r;i<=Q;i++){
		x=rd(),y=rd(),l=rd(),r=rd();
		if(st[x]>st[y])swap(x,y);
		if(LCA(x,y)==x)q[i]=(Query){0,l,r,st[x],st[y],i};
		else q[i]=(Query){LCA(x,y),l,r,ed[x],st[y],i};
	}
	sort(q+1,q+Q+1);
	for(int i=1,l=1,r=0;i<=Q;i++){
		while(l<q[i].x)Rev(id[l++]);
		while(l>q[i].x)Rev(id[--l]);
		while(r<q[i].y)Rev(id[++r]);
		while(r>q[i].y)Rev(id[r--]);
		if(q[i].tp)Rev(q[i].tp);
		ans[q[i].id]=Que(q[i].l,q[i].r);
		if(q[i].tp)Rev(q[i].tp);
	}
	for(int i=1;i<=Q;i++)printf("%d\n",ans[i]);
}