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>

#define pb push_back
#define mp make_pair
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

int readint(){
	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;
}

int n,m,tot,blo,mcnt,ncnt;
int v[600005],nxt[600005],h[300005],eu[600005],st[300005],ed[300005],a[300005],bl[300005],lf[1005],rg[1005];
int dep[300005],now[300005],sum[1005],f[300005][20],ans[300005];
bool vis[300005];

struct node{
	int l,r,x,y,opt,id;
	bool operator<(const node c)const{return l/blo==c.l/blo?(l/blo%2==0?r<c.r:r>c.r):l/blo<c.l/blo;}
}q[300005];

void addedge(int x,int y){
	v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}

void change(int x){
	now[a[x]]^=1;
	if(now[a[x]]==1) sum[bl[a[x]]]++;
	else sum[bl[a[x]]]--;
}

int find(int l,int r,int x){
	int lb=bl[l],rb=bl[r];
	if(lb==rb){
		for(int i=l;i<=r;i++) if(now[i]^(i==x)) return i;
		return -1;
	}
	for(int i=l;i<=rg[lb];i++) if(now[i]^(i==x)) return i;
	for(int i=lf[rb];i<=r;i++) if(now[i]^(i==x)) return i;
	for(int i=lb+1;i<=rb-1;i++){
		if(lf[i]<=x&&x<=rg[i]){
			for(int j=lf[i];j<=rg[i];j++) if(now[j]^(j==x)) return j;
		}
		else if(sum[i]){
			for(int j=lf[i];j<=rg[i];j++) if(now[j]^(j==x)) return j;
		}
	}
	return -1;
}

void dfs(int u,int fa){
	eu[++ncnt]=u,st[u]=ncnt;
	for(int i=1;i<=19;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int p=h[u];p;p=nxt[p]){
		if(v[p]==fa) continue;
		f[v[p]][0]=u,dep[v[p]]=dep[u]+1;
		dfs(v[p],u);
	}
	eu[++ncnt]=u,ed[u]=ncnt;
}

int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}

void init(){
	blo=sqrt(n);
	for(int i=1;i<=n;i+=blo) lf[++mcnt]=i,rg[mcnt]=min(i+blo-1,n);
	for(int i=1;i<=mcnt;i++) for(int j=lf[i];j<=rg[i];j++) bl[j]=i;
}

int main(){
	n=readint(); m=readint();
	blo=sqrt(2*n);
	for(int i=1;i<=n;i++) a[i]=readint();
	for(int i=1;i<n;i++) addedge(readint(),readint());
	dep[1]=1; dfs(1,-1);
	int x,y,z,w;
	for(int i=1;i<=m;i++){
		x=readint(); y=readint(); z=readint(); w=readint();
		if(st[x]>st[y]) swap(x,y);
		int l=lca(x,y);
		q[i].x=z,q[i].y=w;
		if(l==x) q[i].l=st[x],q[i].r=st[y],q[i].id=i,q[i].opt=0;
		else q[i].l=ed[x],q[i].r=st[y],q[i].id=i,q[i].opt=l;
	}
	sort(q+1,q+m+1);
	init();
	int nl=1,nr=0;
	for(int i=1;i<=m;i++){
		while(nl>q[i].l) change(eu[--nl]);
		while(nr<q[i].r) change(eu[++nr]);
		while(nl<q[i].l) change(eu[nl++]);
		while(nr>q[i].r) change(eu[nr--]);
		ans[q[i].id]=find(q[i].x,q[i].y,a[q[i].opt]);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}