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 ("O3")
#define MAXN 300009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
 
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
vector<int>adj[MAXN];
pair<PII,PII>query[MAXN];
const int LOG=19;
int st[MAXN],en[MAXN],id[MAXN<<1],T;
int L[MAXN],R[MAXN],arr[MAXN],ans[MAXN];
int lca[MAXN],P[MAXN][LOG],lvl[MAXN];
int la[MAXN],ra[MAXN];
void dfs(int nd=1,int pr=-1){
	st[nd]=++T;
	id[T]=nd;
	tr(it,adj[nd])
		if(*it!=pr){
			P[*it][0]=nd;
			lvl[*it]=lvl[nd]+1;
			dfs(*it,nd);
		}
	en[nd]=++T;
	id[T]=nd;
}
int LCA(int u,int v){
	if(lvl[u]<lvl[v])swap(u,v);
	for(int i=LOG-1;i>=0;i--)
		if(P[u][i] and lvl[P[u][i]]>=lvl[v])
			u=P[u][i];
	if(u==v)return u;
	for(int i=LOG-1;i>=0;i--)
		if(P[u][i] and P[v][i]!=P[u][i])
			u=P[u][i],v=P[v][i];
	return P[u][0];
}	
int small[MAXN],big[MAXN],parity[MAXN];
const int BLOK=1500;
const int K=775;
void work(int nd){nd=arr[nd]-1;
	parity[nd]^=1;
	big[nd/BLOK]+=2*parity[nd]-1;
	small[nd]=parity[nd];
}
int get(int l,int r){l--;r--;int ans=-1;
	while(l<=r and l%BLOK){if(small[l]){ans=l+1;break;}l++;}
	while(ans==-1 and l+BLOK-1<=r){
		if(big[l/BLOK]){
			while(!small[l])l++;
			ans=l+1;
		}l+=BLOK;
	}
	while(ans==-1 and l<=r){if(small[l]){ans=l+1;break;}l++;}
	return ans;
}
bool cmp(pair<PII,PII>x,pair<PII,PII>y){
	if(x.ff.ff/K!=y.ff.ff/K)	
		return (x.ff.ff<y.ff.ff);
	return (x.ff.ss<y.ff.ss);
}
int main(){
    //freopen("file.in", "r", stdin);
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    	scanf("%d",arr+i);
    for(int i=1;i<n;i++){
    	int u,v;
		scanf("%d%d",&u,&v);
		adj[u].pb(v);
		adj[v].pb(u);	
    }
    dfs();
	for(int j=1;j<LOG;j++)
	    for(int i=1;i<=n;i++)
			if(P[i][j-1])
				P[i][j]=P[P[i][j-1]][j-1];
    for(int i=1;i<=q;i++){
    	int u,v;
    	scanf("%d%d%d%d",&u,&v,la+i,ra+i);
    	lca[i]=LCA(u,v);
    	int l,r,f=0;
    	if(st[u]>st[v])swap(u,v);
    	if(u==lca[i])l=st[u],r=st[v];
    	else l=en[u],r=st[v],f=1;
    	query[i]=mp(mp(l,r),mp(i,f));
    }
    sort(query+1,query+q+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=q;i++){
		int r=query[i].ff.ss,l=query[i].ff.ff;
		int ind=query[i].ss.ff,f=query[i].ss.ss;
		while(L>l)work(id[--L]);
		while(R<r)work(id[++R]);
		while(L<l)work(id[L++]);
		while(R>r)work(id[R--]);
		if(f)work(lca[ind]);
		ans[ind]=get(la[ind],ra[ind]);
		if(f)work(lca[ind]);
    }
    for(int i=1;i<=q;i++)
    	printf("%d\n",ans[i]);
	return 0;
}