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;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
int n,m;
const int xx=3e5+5;
int a[xx];
struct node
{
	int next,to;
}e[xx<<1];
int cnt;
int h[xx];
void add(int x,int y)
{
	cnt++;
	e[cnt].next=h[x];
	h[x]=cnt;
	e[cnt].to=y;
}
int cst;
int in[xx],out[xx],dfx[xx<<1],size[xx],son[xx],dep[xx],f[xx],top[xx];
void dfs(int x,int y)
{
	dfx[++cst]=x;
	in[x]=cst;
	size[x]=1;
	dep[x]=dep[y]+1;
	f[x]=y;
	int maxx=-1;
	for(int i=h[x];i;i=e[i].next)
	{
		if(e[i].to==y)continue;
		dfs(e[i].to,x);
		size[x]+=size[e[i].to];
		if(size[e[i].to]>maxx)maxx=size[e[i].to],son[x]=e[i].to;
	}
	dfx[++cst]=x;
	out[x]=cst;
}
void dfs2(int x,int y)
{
	top[x]=y;
	if(!son[x])return;
	dfs2(son[x],y);
	for(int i=h[x];i;i=e[i].next)
	{
		if(e[i].to==f[x]||e[i].to==son[x])continue;
		dfs2(e[i].to,e[i].to);
	}
}
int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		x=f[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
int B;
int bel(int x){return (x-1)/B+1;}
int rs(int x){return min(n,bel(x)*B);}
int ls(int x){return (bel(x)-1)*B+1;}
struct nod
{
	int l,r,lca,x,y,id;
	bool operator<(const nod&w)const{return bel(l)==bel(w.l)?bel(l)&1?r<w.r:r>w.r:l<w.l;}
}q[xx];
int b[xx];
int t[xx],res[xx];
void add(int x)//加和减是一样的 
{
	if(!x)return;
//	cout<<x<<" ss "<<a[dfx[x]]<<"\n";
	b[bel(a[dfx[x]])]-=t[a[dfx[x]]];
	t[a[dfx[x]]]^=1;
	b[bel(a[dfx[x]])]+=t[a[dfx[x]]];
}
int main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<n;i++)
	{
		int a,b;
		a=read();
		b=read();
		add(a,b);
		add(b,a);
	}
	B=sqrt(n+n);
	dfs(1,0);
	dfs2(1,1);
	for(int i=1;i<=m;i++)
	{
		int a,b,c,d;
		a=read();b=read();
		c=read();d=read();
//		cout<<in[a]<<" "<<in[b]<<" "<<out[a]<<" "<<out[b]<<"\n";
		q[i].id=i;q[i].x=c;q[i].y=d;
		if(dep[a]>dep[b])swap(a,b);
		if(in[a]<=in[b]&&out[b]<=out[a])q[i].l=in[a],q[i].r=in[b];
		else 
		{
			if(in[a]>in[b])swap(a,b);
//			puts("qweqwewqeqwe");
			q[i].lca=lca(a,b);q[i].l=in[a]+1,q[i].r=in[b];
		}
	}
	sort(q+1,q+m+1);////////////////
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(r<q[i].r)add(++r);
		while(l>q[i].l)add(--l);
		while(r>q[i].r)add(r--);
		while(l<q[i].l)add(l++);
		add(in[q[i].lca]);
//		puts("qweqeqeqwe");
		int vis=0;
		if(bel(q[i].x)==bel(q[i].y))
		{
			for(int j=q[i].x;j<=q[i].y;j++)if(t[j])res[q[i].id]=j,vis=1;
		}
		else 
		{
//			cout<<bel(q[i].x)<<" aaa "<<bel(q[i].y)<<"\n";
//			puts("QWWQQQQQQQQQ");
			if(!vis)for(int j=q[i].x;j<=rs(q[i].x);j++)if(t[j])res[q[i].id]=j,vis=1;
			if(!vis)for(int j=ls(q[i].y);j<=q[i].y;j++)if(t[j])res[q[i].id]=j,vis=1;
			if(!vis)
			for(int j=bel(q[i].x)+1;j<=bel(q[i].y)-1;j++)
			if(b[j])
			{
				for(int s=(j-1)*B+1;;s++)
				{
					if(t[s])
					{
						res[q[i].id]=s,vis=1;
						break;
					}
				}
				break;
			}
		}
		if(!vis)res[q[i].id]=-1;
//		cout<<q[i].l<<" "<<q[i].r<<" "<<q[i].lca<<" "<<q[i].x<<" "<<q[i].y<<"\n";
//		puts("");
		add(in[q[i].lca]);
	}
	for(int i=1;i<=m;i++)cout<<res[i]<<"\n";
	return 0;
}