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:
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1200010;
char __buf[1<<20],*__p1,*__p2;
#define getchar() (__p1==__p2?(__p2=__buf+fread(__p1=__buf,1,1<<20,stdin),__p1==__p2?EOF:*__p1++):*__p1++)
int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
struct Qu{int l,r,LC,lc,rc,n;}Q[maxn];
int B[maxn],C[maxn],dfn[maxn],low[maxn],N,wc[maxn],d[maxn],fa[maxn][20],n,q,bl,bc,c[maxn],vc[maxn],pr[maxn],ls[maxn],rs[maxn];
char ton[maxn];vector<int>G[maxn];
bool cmp(Qu x,Qu y) {return B[x.l]==B[y.l]?B[x.l]&1?x.r<y.r:x.r>y.r:x.l<y.l;}
void add(int x,int y) {G[x].push_back(y),G[y].push_back(x);}
void Dfs(int x) {
	wc[dfn[x]=++N]=x,d[x]=d[fa[x][0]]+1;
	for(int i=0;fa[x][i];i++) fa[x][i+1]=fa[fa[x][i]][i];
	for(auto y:G[x]) if(y^fa[x][0]) fa[y][0]=x,Dfs(y);
	wc[low[x]=++N]=x;
}
int LCA(int x,int y) {
	if(d[x]<d[y]) swap(x,y);
	for(int i=19;~i;i--) if(d[fa[x][i]]>=d[y]) x=fa[x][i];
	if(x==y) return x;
	for(int i=19;~i;i--) if(fa[x][i]^fa[y][i]) x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void ins(int x) {
	x=c[x];
	if((ton[x]^=1)) ++vc[C[x]];
	else --vc[C[x]];
}
int ask(int l,int r) {
	if(C[l]==C[r]) {
		for(int i=l;i<=r;i++) if(ton[i]) return i;
		return -1;
	}
	for(int i=l;i<=rs[C[l]];i++) if(ton[i]) return i;
	for(int i=ls[C[r]];i<=r;i++) if(ton[i]) return i;
	for(int i=C[l]+1;i<C[r];i++) if(vc[i])
		for(int j=ls[i];j<=rs[i];j++) if(ton[j]) return j;
	return -1;
}
signed main() {
	n=read(),q=read(),bl=pow(q,0.5),bc=sqrt(n);
	for(int i=1;i<=n;i++) c[i]=read(),C[i]=(i-1)/bc+1,C[i]^C[i-1]?ls[C[i]]=i:0,rs[C[i]]=i;
	for(int i=1;i<n;i++) add(read(),read());
	Dfs(1);for(int i=1;i<=N;i++) B[i]=(i-1)/bl+1;
	for(int i=1,x,y,lc;i<=q;i++) {
		lc=LCA(x=read(),y=read()),dfn[x]>dfn[y]?swap(x,y):void();
		if(lc==x||lc==y) Q[i]=(Qu){dfn[x],dfn[y],0,read(),read(),i};
		else Q[i]=(Qu){low[x],dfn[y],lc,read(),read(),i};
	}
	sort(Q+1,Q+1+q,cmp);
	int L=1,R=0;
	for(int i=1;i<=q;i++) {
		while(R<Q[i].r) ins(wc[++R]);
		while(Q[i].l<L) ins(wc[--L]);
		while(R>Q[i].r) ins(wc[R--]);
		while(Q[i].l>L) ins(wc[L++]);
		if(Q[i].LC) ins(Q[i].LC);
		pr[Q[i].n]=ask(Q[i].lc,Q[i].rc);
		if(Q[i].LC) ins(Q[i].LC);
	}
	for(int i=1;i<=q;i++) cout<<pr[i]<<'\n';
	return 0;
}