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:
//George1123
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef vector<int> vi;
typedef pair<int,int> pii;

#define x first
#define y second
#define sz(a) (int)((a).size())
#define all(a) (a).begin(),(a).end()
#define R(i,n) for(int i=0;i<(n);++i)
#define L(i,n) for(int i=(n)-1;i>=0;--i)

constexpr int inf32=0x3f3f3f3f;
constexpr i64 inf64=0x3f3f3f3f3f3f3f3f;

constexpr int mod=1e9+7;

struct mint{
	int x;
	mint(int x=0):x(x){}

	friend mint operator+
	(const mint a,const mint &b){
		int x=a.x+b.x;
		return mint(x>=mod?x-mod:x);
	}

	friend mint operator-
	(const mint a,const mint &b){
		int x=a.x-b.x;
		return mint(x<0?x+mod:x);
	}
	
	friend mint operator*
	(const mint a,const mint &b){
		return mint(1ll*a.x*b.x%mod);
	}
};

int mypow(int a,int x=mod-2,int res=1){
	for(;x;x>>=1,a=(mint(a)*a).x)
		if(x&1) res=(mint(res)*a).x;
	return res;
}

vi pw;
void hash_init(int n){
	pw.assign(n,0),pw[0]=1;
	R(i,n)if(i) pw[i]=(mint(pw[i-1])*2).x;
}

struct keyt{
	int sm;
	keyt *ls,*rs;
	keyt(int sm):sm(sm),ls(0),rs(0){}
};

keyt *build(int l,int r){
	keyt *u=new keyt(0);
	if(r-l==1) return u;
	int m=l+r>>1;
	u->ls=build(l,m),u->rs=build(m,r);
	return u;
}

keyt *add(keyt *&u,int i,int l,int r){
	if(r<=i||i<l) return u;
	keyt *v=new keyt(u->sm^pw[i]);
	if(r-l==1) return v;
	int m=l+r>>1;
	v->ls=add(u->ls,i,l,m);
	v->rs=add(u->rs,i,m,r);
	return v;
}

int get(keyt *&u,keyt *&v,keyt *&f,
keyt *&g,int x,int y,int l,int r){
	if(r<=x||y<=l) return -1;
	if(!(u->sm^v->sm^f->sm^g->sm)) return -1;
	if(r-l==1) return l;
	int res=-1,m=l+r>>1;
	if(~(res=get(u->ls,v->ls,f->ls,
		g->ls,x,y,l,m))) return res;
	return get(u->rs,v->rs,f->rs,g->rs,x,y,m,r);
}

struct tree{
	int n,k;
	vi d,a;
	vector<keyt *> rt;
	vector<vi> fa,adj;
	tree(int n):k(log2(n)+2),n(n),a(n),
	d(n+1,-1),fa(k,vi(n+1,n)),adj(n),rt(n+1){}
	int &father(int u){return fa[0][u];}
	void adde(int u,int v){
		adj[u].push_back(v);
		adj[v].push_back(u);
	} 
	
	void dfs(int u){
		R(i,k-1) fa[i+1][u]=fa[i][fa[i][u]];
		rt[u]=add(rt[father(u)],a[u],0,n);
		for(const int &v:adj[u]){
			if(v==father(u)) continue;
			father(v)=u,d[v]=d[u]+1,dfs(v);
		}
	}
	
	int lca(int u,int v){
		if(d[u]<d[v]) swap(u,v);
		L(i,k)if(d[fa[i][u]]>=d[v]) u=fa[i][u];
		if(u==v) return u;
		L(i,k)if(fa[i][u]!=fa[i][v]) 
			u=fa[i][u],v=fa[i][v];
		return father(u);
	}
	
	void init(){
		rt[n]=build(0,n);
		d[0]=0,dfs(0);
	}
	
	void check(){
		R(i,n+1) cout<<d[i]<<" \n"[i==n];
		R(i,k)R(j,n+1) cout<<fa[i][j]<<" \n"[j==n];
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	int n,q;
	cin>>n>>q;
	hash_init(n);
	tree T(n);
	R(i,n) cin>>T.a[i],--T.a[i];
	R(i,n-1){
		int u,v;
		cin>>u>>v,--u,--v;
		T.adde(u,v);
	}
	T.init();
//	T.check();
	
	while(q--){  
		int u,v,l,r;
		cin>>u>>v>>l>>r,--u,--v,--l;
		int lca=T.lca(u,v);
		int res=get(T.rt[u],T.rt[v],T.rt
		[lca],T.rt[T.father(lca)],l,r,0,n);
		
		if(!~res) cout<<"-1\n";
		else cout<<res+1<<'\n';
	}
	
	return 0;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/