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>
#pragma GCC optimize (2)
using namespace std;
const int maxn=6e5+13; 
int bel[maxn];
vector<int> eg[maxn]; 
struct Q{
	int l,r,f,num,ql,qr;
}tt[maxn];
int fir[maxn],las[maxn],cnt[maxn];
int fa[maxn][30],lg[maxn+5];
int dep[maxn],ans[maxn];
int p[maxn],a[maxn],vis[maxn];
int tot,sz2;//sz2是第二次分块每个块的大小 
int b[maxn],bl[maxn];//b表示每一个块内符合情况数的个数,每一个块的奇偶性 
void pre()
{
	for(int i=1;i<=300013;i++) lg[i]=lg[i>>1]+1; 
}
void dfs(int x,int f) 
{
	p[fir[x]=++tot]=x;
	fa[x][0]=f,dep[x]=dep[f]+1;
	for(int i=1;i<=20;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=0;i<eg[x].size();i++)
	{
		int v=eg[x][i];
		if(v!=f) dfs(v,x);
	}
	p[las[x]=++tot]=x;
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y])
	{
		x=fa[x][lg[dep[x]-dep[y]]];
	}
	if(x==y) return y;
	for(int i=20;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i],y=fa[y][i];
		}
	}
	return fa[x][0];
}
bool cmp(Q a,Q b)
{
	return bel[a.l]==bel[b.l]?(bel[a.l]&1?a.r<b.r:a.r>b.r):bel[a.l]<bel[b.l]; 
 }
int query(int l,int r){
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;i++){
			if(cnt[i]&1) return i;
		}
	}
	else{
		for(int i=l;i<=bl[l]*sz2;i++){
			if(cnt[i]&1) return i; 
		}
		for(int i=(bl[r]-1)*sz2+1;i<=r;i++){
			if(cnt[i]&1) return i;
		}
		for(int i=bl[l]+1;i<=bl[r]-1;i++){
			if(b[i]){
				for(int j=sz2*(i-1)+1;j<=sz2*i;j++){
					if(cnt[j]&1) return j;
				}
			}
		}
	}
	return -1;
}
void work(int t){
	int x=a[t];
	if(cnt[x]&1) b[bl[x]]--;
    cnt[x]^=1;
    if(cnt[x]&1) b[bl[x]]++;
}
int main()
{
	lg[0]=-1;
	pre();
    int n,m,u,v,l,r;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n-1;i++)
	{
		scanf("%d%d",&u,&v);
		eg[v].push_back(u);
		eg[u].push_back(v);
		}
    dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&l,&r);
		if(fir[u]>fir[v]) swap(u,v);
		int f1=lca(u,v);
		if(f1==u||f1==v)
		{
			tt[i]=(Q){fir[u],fir[v],0,i,l,r};
		 } 
		else{
			tt[i]=(Q){las[u],fir[v],f1,i,l,r};
		}
		}
	l=1,r=0;
	int num=(int)sqrt(2*n);
	for(int i=1;i<=2*n;i++)
	{
	 bel[i]=i/num+1;
	}
	sort(tt+1,tt+1+m,cmp);
	sz2=(int)sqrt(1.0*n);
	for(int i=1;i<=n;i++){
		bl[i]=(i-1)/sz2+1;
	}
	for(int i=1;i<=m;i++)
	{
		while(l>tt[i].l) work(p[--l]);
		while(r<tt[i].r) work(p[++r]);
		while(l<tt[i].l) work(p[l++]);
		while(r>tt[i].r) work(p[r--]);
		if(tt[i].f) work(tt[i].f); 
		ans[tt[i].num]=query(tt[i].ql,tt[i].qr);
		if(tt[i].f) work(tt[i].f);
	 }
	 for(int i=1;i<=m;i++) printf("%d\n",ans[i]);	
}