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 forr(i,a,b) for(int i=(a);i<(b);i++)
#define forn(i,n) forr(i,0,n)
#define dforn(i,n) for(int i=n-1;i>=0;i--)
#define forall(it,v) for(auto it=v.begin();it!=v.end();it++)
#define sz(c) ((int)c.size())
#define rsz resize
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fst first
#define snd second

#ifdef ANARAP
#define MAXN 3000
#else
#define MAXN 300010
#endif

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

int v[MAXN];
vector<int> g[MAXN];

const int LOGN=20;
//f[v][k] holds the 2^k father of v
//L[v] holds the level of v
int N, f[MAXN][LOGN], L[MAXN];
//call before build:
void dfs(int v, int fa=-1, int lvl=0){//generate required data
	f[v][0]=fa, L[v]=lvl;
	forall(it, g[v])if(*it!=fa) dfs(*it, v, lvl+1); }
void build(){//f[i][0] must be filled previously, O(nlgn)
	forn(k, LOGN-1) forn(i, N) f[i][k+1]=f[f[i][k]][k];}
#define lg(x) (31-__builtin_clz(x))//=floor(log2(x))
int climb(int a, int d){//O(lgn)
	if(!d) return a;
	dforn(i, lg(L[a])+1) if(1<<i<=d) a=f[a][i], d-=1<<i;
    return a;
}
int lca(int a, int b){//O(lgn)
	if(L[a]<L[b]) swap(a, b);
	a=climb(a, L[a]-L[b]);
	if(a==b) return a;
	dforn(i, lg(L[a])+1) if(f[a][i]!=f[b][i]) a=f[a][i], b=f[b][i];
	return f[a][0];
}

struct tipo{
	int id, tam;
	ll hval;
	bool on;
};

const int P = 1777771, MOD = 999727999;
ll VP[MAXN];
const tipo NEUT = {-1,0,0,false};
tipo oper(tipo a, tipo b) {
	return {-1, a.tam+b.tam, (a.hval + b.hval*VP[a.tam])%MOD, false};
}
struct STree { // persistent segment tree for min over integers
	vector<tipo> st;
	vector<int> L, R; int n,rt,cursz;
	STree(int n=0): st(1,NEUT),L(1,0),R(1,0),n(n),rt(0),cursz(1){}
	int new_node(tipo v, int l=0, int r=0){
		int ks=sz(st);
		st.pb(v);L.pb(l);R.pb(r);
		return ks;
	}
	int init(int s, int e){ // not necessary in most cases
		if(s+1==e)return new_node(NEUT);
		int m=(s+e)/2,l=init(s,m),r=init(m,e);
		return new_node(oper(st[l],st[r]),l,r);
	}
	int upd(int k, int s, int e, int p){
		int ks=new_node(st[k],L[k],R[k]);
		if(s+1==e){st[ks]={s, 1-st[ks].tam, e*(1-st[ks].tam), !st[ks].on};return ks;}
		int m=(s+e)/2,ps;
		if(p<m)ps=upd(L[ks],s,m,p),L[ks]=ps;
		else ps=upd(R[ks],m,e,p),R[ks]=ps;
		st[ks]=oper(st[L[ks]],st[R[ks]]);
		return ks;
	}
	tipo query(int k, int s, int e, int a, int b){
		if(e<=a||b<=s)return NEUT;
		if(a<=s&&e<=b)return st[k];
		int m=(s+e)/2;
		return oper(query(L[k],s,m,a,b),query(R[k],m,e,a,b));
	}
	int solve(int l, int r, int k1, int k2, int s, int e){
		if(s+1 == e){
			assert(st[k1].on != st[k2].on);
			return e;
		}
		int m = (s+e)>>1;
		if(r <= m) return solve(l, r, L[k1], L[k2], s, m);
		else if(l >= m) return solve(l, r, R[k1], R[k2], m, e);
		else {
			if(query(L[k1], s, m, l, m).hval != query(L[k2], s, m, l, m).hval) return solve(l, m, L[k1], L[k2], s, m);
			return solve(m, r, R[k1], R[k2], m, e);
		}
	}
	int init(){return init(0,n);}
	int upd(int k, int p){return rt=upd(k,0,n,p);}
	int upd(int p){return upd(rt,p);} // update on last root
	tipo query(int k, int a, int b){return query(k,0,n,a,b);};
}; // usage: STree rmq(n);root=rmq.init(x);new_root=rmq.upd(root,i,v);rmq.query(root,s,e);

int roots[MAXN];
int n;
STree st;

void dfs1(int x, int p)
{
	roots[x] = st.upd(roots[p], v[x]);
	forall(it, g[x]) if(*it != p) dfs1(*it, x);
}

int main()
{
	#ifdef ANARAP
		freopen("input.in", "r", stdin);
		//freopen("output.out", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	VP[0] = 1;
	forr(i,1,MAXN) VP[i] = VP[i-1]*P%MOD;
	int q;
	cin >> n >> q;
	N = n;
	forn(i,n)
	{
		cin >> v[i];
		v[i]--;
	}
	forn(i,n-1)
	{
		int a,b;
		cin >> a >> b;
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	st = STree(n);
	//roots[0] = st.init();
	dfs1(0,0);
	dfs(0);
	build();
	forn(i,q)
	{
		int a,b,l,r;
		cin >> a >> b >> l >> r;
		a--;b--;l--;
		int aux = st.upd(roots[a], v[lca(a,b)]);
		//cout << st.query(aux,l,r).hval << ' ' << st.query(roots[b],l,r).hval << '\n';
		if(st.query(aux,l,r).hval == st.query(roots[b],l,r).hval) cout << "-1\n";
		else cout << st.solve(l, r, aux, roots[b], 0, n) << endl;
	}
	return 0;
}