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 ll long long
#define N 600015
#define B 776
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
using namespace std;
int n,m,a[N],cnt[N],ccnt[N];
VI e[N];
int st[N],ed[N],rev[N],clk;
int fa[N][25],dep[N];
struct query{
	int l,r,L,R,lca,id;
	bool operator <(const query& rhs) const{
		if(l/B != rhs.l/B) return l/B < rhs.l/B;
		if((l/B)&1) return r/B < rhs.r/B;
		return r/B > rhs.r/B;
	}
}q[N];
void dfs(int u,int f){
	fa[u][0] = f; dep[u] = dep[f]+1; st[u] = ++clk; rev[clk] = u;
	rep(i,1,19) fa[u][i] = fa[fa[u][i-1]][i-1];
	for(auto v:e[u]) if(v != f){
		dfs(v,u);
	}
	ed[u] = ++clk; rev[clk] = u;
}
int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	int d = dep[u]-dep[v];
	rep(i,0,19) if((1<<i)&d) u = fa[u][i];
	if(u == v) return u;
	per(i,0,19){
		if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
	}
	return fa[u][0];
}
void getq(){
	rep(i,1,m){
		int u,v,l,r; scanf("%d%d%d%d",&u,&v,&l,&r);
		int LCA = lca(u,v);
		q[i].id = i; q[i].L = l,q[i].R = r;
		if(st[u] > st[v]) swap(u,v);
		if(u == LCA) q[i].l = st[u],q[i].r = st[v];
		else q[i].l = ed[u],q[i].r = st[v],q[i].lca = LCA;
	}
	sort(q+1,q+m+1);
}
int ans[N];
void add(int x){
	if(cnt[x]) ccnt[x/B]--;
	else ccnt[x/B]++;
	cnt[x] ^= 1;
}
int getans(int l,int r){
	rep(i,l/B+1,r/B-1){
		if(!ccnt[i]) continue;
		rep(j,i*B,i*B+B-1) if(cnt[j]) return j;
	}
	int R = l/B*B+B-1,L = r/B*B;
	rep(i,l,min(r,R)) if(cnt[i]) return i;
	rep(i,max(l,L),r) if(cnt[i]) return i;
	return -1;
}
void solve(){
	for(int i = 1,l = 1,r = 0;i <= m;++i){
		while(l > q[i].l) add(a[rev[--l]]);
		while(r < q[i].r) add(a[rev[++r]]);
		while(l < q[i].l) add(a[rev[l++]]);
		while(r > q[i].r) add(a[rev[r--]]);
		if(q[i].lca) add(a[q[i].lca]);
		ans[q[i].id] = getans(q[i].L,q[i].R);
		if(q[i].lca) add(a[q[i].lca]);
	}
	rep(i,1,m) printf("%d\n",ans[i]);
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
 	scanf("%d%d",&n,&m);
 	rep(i,1,n) scanf("%d",&a[i]);
 	rep(i,2,n){ int u,v; scanf("%d%d",&u,&v);
 		e[u].pb(v); e[v].pb(u);
 	}
 	dfs(1,0);
 	getq();
 	solve();
	return 0;
}