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 gc getchar
#define pc putchar
#define N 300005
using namespace std;
template<class T>void read(T&x) {
	T f=1;x=0;char c=gc();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc();}
	while('0'<=c&&c<='9'){x=x*10+c-'0';c=gc();}
	x*=f;
}
template<class T>void print(T x,char c) {
	if(x<0)pc('-'),x=-x;int s[20],top=0;
	while(s[++top]=x%10,x/=10);
	while(top)pc(s[top--]+'0');pc(c);
}
int n,m,cnt,blk,B,h[N],a[N],col[N<<1];
struct Edge{int to,next;}e[N<<1];
void Add(int x,int y) {
	cnt++;e[cnt].to = y;e[cnt].next = h[x];h[x] = cnt;
}
int dfn[N<<1],st[N],ed[N],step,fa[N],dep[N],siz[N],son[N],top[N];
void dfs1(int x,int f) {
	fa[x] = f;dep[x] = dep[f]+1;siz[x] = 1;
	for(int i=h[x]; i; i=e[i].next) {
		int y = e[i].to;
		if(y != f) {
			dfs1(y,x);siz[x] += siz[y];
			if(siz[y] > siz[son[x]])son[x] = y;
		}
	}
}
void dfs2(int x,int tp) {
	top[x] = tp;dfn[++step] = x;st[x] = step;
	if(son[x])dfs2(son[x],tp);
	for(int i=h[x]; i; i=e[i].next) {
		int y = e[i].to;
		if(y != fa[x] && y != son[x])dfs2(y,y);
	}
	dfn[++step] = x;ed[x] = step;
}
int LCA(int x,int y) {
	while(top[x] != top[y]) {
		if(dep[top[x]] < dep[top[y]])swap(x,y);
		x = fa[top[x]];
	}
	if(dep[x] < dep[y])return x;
	return y;
}
struct query {
	int l,r,L,R,id,lca;
	bool operator < (const query &b)const {
		return l/blk==b.l/blk?l/blk&1?r<b.r:r>b.r:l<b.l;
	}
}q[N];
struct change {
	int pos,pre,now;
}c[N];
int Ans[N],vst[N],num[N],sum[N],pos[N],L[N],R[N];
void change(int x) {
	num[x] ^= 1;
	if(num[x])sum[pos[x]]++;
	else sum[pos[x]]--;
}
void Move(int x){change(a[x]);}
int ask(int l,int r) {
	int p = pos[l],q = pos[r];
	if(p == q) {
		if(sum[p])for(int i=l; i<=r; ++i)if(num[i])return i;
		return -1;
	}
	if(sum[p])for(int i=l; i<=R[p]; ++i)if(num[i])return i;
	if(sum[q])for(int i=L[q]; i<=r; ++i)if(num[i])return i;
	for(int i=p+1; i<q; ++i)if(sum[i]) {
		for(int j=L[i]; j<=R[i]; ++j)
			if(num[j])return j;
	}
	return -1;
}
int main() {
	read(n),read(m);
	for(int i=1; i<=n; ++i)read(a[i]);
	for(int i=1,x,y; i<n; ++i)read(x),read(y),Add(x,y),Add(y,x);
	dfs1(1,0);dfs2(1,0);blk = pow(m,0.5);B = 500;
	for(int i=1; i<=600; ++i) {
		L[i] = (i-1)*B+1;R[i] = i*B;
		for(int j=L[i]; j<=R[i]; ++j)
			pos[j] = i;
	}
//	for(int i=1; i<=2*n; ++i)cerr << dfn[i] << ' ';
//	cerr << '\n';
	for(int i=1,u,v,l,r,z; i<=m; ++i) {
		read(u),read(v),read(l),read(r);
		z = LCA(u,v);if(st[u] > st[v])swap(u,v);
		if(u == z)q[i] = (query){st[u],st[v],l,r,i};
		else q[i] = (query){ed[u],st[v],l,r,i,z};
	}
	sort(q+1,q+m+1);
	for(int i=1,l=1,r=0; i<=m; ++i) {
		while(r < q[i].r)Move(dfn[++r]);
		while(l > q[i].l)Move(dfn[--l]);
		while(r > q[i].r)Move(dfn[r--]);
		while(l < q[i].l)Move(dfn[l++]);
		if(q[i].lca)Move(q[i].lca);
		Ans[q[i].id] = ask(q[i].L,q[i].R);
		if(q[i].lca)Move(q[i].lca);
	}
	for(int i=1; i<=m; ++i)print(Ans[i],'\n');
}