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;
template <typename T> void read(T &t) {
	t=0; char ch=getchar(); int f=1;
	while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
	do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
typedef unsigned long long ull;
const int INF=1e6;
const int maxn=(3e5)+10;
const int maxm=(1e7)+10;
int n,m,a[maxn],fa[maxn][20],dep[maxn],tot,head[maxn],nxt[maxn*2],to[maxn*2];
int rt[maxn],ls[maxm],rs[maxm];
void add(int x,int y) {
	tot++; nxt[tot]=head[x];
	head[x]=tot; to[tot]=y;
}
int lca(int x,int y) {
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=19;i>=0;i--)
		if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
	if (x==y) return x;
	for (int i=19;i>=0;i--)
		if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
ull haxi[maxn],tr[maxm];
ull get() {
	ull res=0;
	for (int i=0;i<=62;i++)
		if (rand()&1) res|=((ull)1<<i);
	return res;
}
void add(int x,int l,int r,int &root,ull delta) {
	tot++; ls[tot]=ls[root],rs[tot]=rs[root],tr[tot]=(tr[root]^delta);
	root=tot;
	if (l==r) return;
	int mid=(l+r)>>1;
	if (x<=mid) add(x,l,mid,ls[root],delta);
	else add(x,mid+1,r,rs[root],delta);
}
void dfs(int u,int p) {
	dep[u]=dep[p]+1,fa[u][0]=p;
	rt[u]=rt[p];
	add(a[u],1,n,rt[u],haxi[a[u]]);
	for (int i=head[u],v;i;i=nxt[i]) {
		v=to[i];
		if (v==p) continue;
		dfs(v,u);
	}
}
int query(int L,int R,int l,int r,int x,int y,int delta) {
	if (l>R||r<L) return -1;
	int mid=(l+r)>>1;
	if (L<=l&&r<=R) {
		ull h=0; if (l<=delta&&delta<=r) h=haxi[delta];
		if ((tr[x]^tr[y]^h)==0) return -1;
		if (l==r) return l;
		ull lh=0; if (l<=delta&&delta<=mid) lh=haxi[delta];
		if (tr[ls[x]]^tr[ls[y]]^lh) return query(L,R,l,mid,ls[x],ls[y],delta);
		return query(L,R,mid+1,r,rs[x],rs[y],delta);
	}
	int t1=query(L,R,l,mid,ls[x],ls[y],delta);
	if (t1!=-1) return t1;
	int t2=query(L,R,mid+1,r,rs[x],rs[y],delta);
	return t2;
}
int main() {
	//freopen("1.txt","r",stdin);
	srand(time(0));
	read(n); read(m); int x,y,z;
	for (int i=1;i<=n;i++) read(a[i]);
	for (int i=1;i<n;i++) {
		read(x),read(y);
		add(x,y),add(y,x);
	}
	for (int i=1;i<=n;i++) {
		haxi[i]=get();
	}
	tot=0;
	dfs(1,0);
	for (int i=1;i<=19;i++) for (int j=1;j<=n;j++)
		fa[j][i]=fa[fa[j][i-1]][i-1];
	int l,r;
	while (m--) {
		read(x),read(y); read(l); read(r);
		z=lca(x,y);
		printf("%d\n",query(l,r,1,n,rt[x],rt[y],a[z]));
	}
	return 0;
}
/*
  0. Enough array size? Enough array size? Enough array size? Integer overflow?
  
  1. Think TWICE, Code ONCE!
  Are there any counterexamples to your algo?
    
  2. Be careful about the BOUNDARIES!
  N=1? P=1? Something about 0?
    
  3. Do not make STUPID MISTAKES!
  Time complexity? Memory usage? Precision error?
*/