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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define N 601000
#define NN 20001000
typedef unsigned long long ull;
template<typename T> inline void read(T &x) {
	x = 0; char c = getchar();
	while (!isdigit(c)) c = getchar();
	while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
}
using namespace std;
int n, q;
int a[N];
struct edge{
	int nxt, to;
	edge(){}
	edge(int jzp, int zzz) { nxt = jzp, to = zzz; }
}e[N];
int head[N], ecnt;
inline void addedge(int from, int to) {
	e[++ecnt] = edge(head[from], to);
	head[from] = ecnt;
}
int dedfn[N], st[N], ed[N], dcnt, siz[N], fa[N], son[N], dep[N];
void dfs_son(int cur, int faa) {
	dedfn[++dcnt] = cur; st[cur] = dcnt;
	siz[cur] = 1, fa[cur] = faa, dep[cur] = dep[faa] + 1;
	int mx = 0;
	for (int i = head[cur]; i; i = e[i].nxt) {
		int to = e[i].to; if (to == faa)	continue;
		dfs_son(to, cur); siz[cur] += siz[to];
		if (siz[to] > mx)	mx = siz[to], son[cur] = to;
	}
	dedfn[++dcnt] = cur; ed[cur] = dcnt;
}
int top[N];
void dfs_chain(int cur, int topp) {
	top[cur] = topp;
	if (!son[cur])	return;
	dfs_chain(son[cur], topp);
	for (int i = head[cur]; i;i = e[i].nxt) {
		int to = e[i].to; if (to == son[cur] || to == fa[cur])	continue;
		dfs_chain(to, to);
	}
}
int get_lca(int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]])	swap(x, y);
		x = fa[top[x]];
	}
	return dep[x] < dep[y] ? x : y;
}

int ls[NN], rs[NN], rt[N], ttot;
ull sum[NN];
inline void pushup(int cur) {
	sum[cur] = sum[ls[cur]] ^ sum[rs[cur]];
}
void ins(int L, int R, int pos, ull v, int lcur, int &cur) {
	cur = ++ttot; sum[cur] = sum[lcur] ^ v;
	if (L == R)	return void();
	ls[cur] = ls[lcur], rs[cur] = rs[lcur];
	int mid = (L + R) >> 1;
	if (pos <= mid)	ins(L, mid, pos, v, ls[lcur], ls[cur]);
	else	ins(mid + 1, R, pos, v, rs[lcur], rs[cur]);
	pushup(cur);
}

int query(int L, int R, int l, int r, int lcur, int rcur) {
	if (L == R)	return sum[rcur] ^ sum[lcur] ? L : L + 1;
	int mid = (L + R) >> 1;
	if (l <= L && R <= r)
		return  sum[ls[lcur]] ^ sum[ls[rcur]] ? query(L, mid, l, r, ls[lcur], ls[rcur]) :
			query(mid + 1, R, l, r, rs[lcur], rs[rcur]);
	if (l <= mid && r > mid) {
		int res = query(L, mid, l, r, ls[lcur], ls[rcur]);
		if (res > mid)	return query(mid + 1, R, l, r, rs[lcur], rs[rcur]);
		return res;
	} else if (l <= mid)	return query(L, mid, l, r, ls[lcur], ls[rcur]);
	else	return query(mid + 1, R, l, r, rs[lcur], rs[rcur]);
}

ull rd[N];
inline ull Rand() {
	return ((1ull * rand()) << 48) ^ ((1ull * rand()) << 32) ^ ((1ull * rand()) << 16) ^ (1ull * rand());
}

int main() {
	srand((long long)new char);
	srand((unsigned)time(0) ^ rand());
	read(n), read(q);
	for (int i = 1; i <= n; ++i)	read(a[i]), rd[i] = Rand();
	for (int i = 1; i < n; ++i) {
		int u, v; read(u), read(v); addedge(u, v), addedge(v, u);
	}
	dfs_son(1, 0), dfs_chain(1, 1);
	for (register int i = 1; i <= dcnt; ++i)
		ins(1, n, a[dedfn[i]], rd[a[dedfn[i]]], rt[i - 1], rt[i]);
	for (int i = 1; i <= q; ++i) {
		int x, y, l, r; read(x), read(y), read(l), read(r);
		if (dep[x] < dep[y])	swap(x, y);
		int lca = get_lca(x, y);
		if (lca == y) {
			int res = query(1, n, l, r, rt[st[y] - 1], rt[st[x]]);
			if (res > r)	puts("-1");
			else	printf("%d\n", res);
		} else {
			int jzp = 0, res;
			if (ed[x] > st[y])	swap(x, y);//ins(1, n, a[lca], rd[a[lca]], rt[st[x]], jzp), res = query(1, n, l, r, rt[ed[y] - 1], jzp);
			ins(1, n, a[lca], rd[a[lca]], rt[st[y]], jzp), res = query(1, n, l, r, rt[ed[x] - 1], jzp);//qy[qtot] = Queries(ed[x], st[y], ttot, qtot);
//			Lca[qtot] = lca;
			if (res > r)	puts("-1");
			else	printf("%d\n", res);
		}
	}
	return 0;
}