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 forn(i,s,t) for(register int i=(s);i<=(t);++i)
using namespace std;
typedef unsigned long long ull;
const int N = 3e5+3, M = N<<5;
struct List {int dir, nxt; } E[N<<1];
int G[N], cnt;
inline void Add(int u, int v) {
	E[++cnt].dir = v, E[cnt].nxt = G[u], G[u] = cnt;
}
int rt[N];
mt19937_64 AKIOI(114514);
class PreSegTree {
	private:
		int L[M], R[M], sl; ull val[M];
	public:
		void Upd(int& p, int pre, int l, int r, int pos, ull k) {
			if(!p) p = ++sl; val[p] = val[pre] ^ k;
			if(l == r) return ;
			int mid = l+r >> 1;
			if(pos <= mid) Upd(L[p], L[pre], l, mid, pos, k), R[p] = R[pre];
			else Upd(R[p], R[pre], mid+1, r, pos, k), L[p] = L[pre];
		}
		int Qry(int p1, int p2, int p3, int p4, int l, int r, int nl, int nr) {
			if((val[p1] ^ val[p2] ^ val[p3] ^ val[p4]) == 0ull) return -1;
			if(nl == nr) return nl;
			int mid = nl+nr >> 1;
			if(l <= mid) {
				int tmp = Qry(L[p1], L[p2], L[p3], L[p4], l, r, nl, mid);
				if(~tmp) return tmp;
			}
			if(r > mid) {
				int tmp = Qry(R[p1], R[p2], R[p3], R[p4], l, r, mid+1, nr);
				if(~tmp) return tmp;
			}
			return -1;
		}
}T;
int n, m, a[N]; ull ton[N];
int sz[N], son[N], top[N], fa[N], dep[N];
void F_dfs(int u) {
	T.Upd(rt[u], rt[fa[u]], 1, n, a[u], ton[a[u]]);
	sz[u] = 1;
	for(register int i=G[u];i;i=E[i].nxt) {
		int v=E[i].dir;
		if(v == fa[u]) continue ;
		fa[v] = u, dep[v] = dep[u] + 1;
		F_dfs(v);
		sz[u] += sz[v];
		if(sz[son[u]] < sz[v]) son[u] = v;
	}
}
void S_dfs(int u, int tp) {
	top[u] = tp; if(!son[u]) return ;
	S_dfs(son[u], tp);
	for(register int i=G[u];i;i=E[i].nxt) {
		int v=E[i].dir;
		if(v == fa[u] || v == son[u]) continue ;
		S_dfs(v, v);
	}
}
inline int Lca(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	return u;
}
int main() {
	scanf("%d%d", &n, &m);
	forn(i,1,n) scanf("%d", a+i);
	forn(i,1,n) ton[i] = AKIOI();
	forn(i,2,n) {
		static int u, v;
		scanf("%d%d", &u, &v);
		Add(u, v), Add(v, u);
	}
	F_dfs(1), S_dfs(1, 1);
	while(m--) {
		static int u, v, l, r;
		scanf("%d%d%d%d", &u, &v, &l, &r);
		int k1 = Lca(u, v), k2 = fa[k1];
		printf("%d\n", T.Qry(rt[u], rt[v], rt[k1], rt[k2], l, r, 1, n));
	}
	return 0;
}