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 debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, q;
int a[N];
vector<int>G[N];
const int S = 500;
int ans[N];
struct Q
{
	int lca, tl, tr, L, R, id;
	bool operator<(const Q& b)const {
		return tl / S == b.tl / S ? tr < b.tr : tl / S < b.tl / S;
	}
}qq[N];
int clk, in[N], out[N], siz[N], fa[N], dep[N], son[N], topf[N], b[N];
void dfs1(int u, int _fa) {
	siz[u] = 1; fa[u] = _fa;
	in[u] = ++clk;
	b[clk] = u;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dep[v] = dep[u] + 1;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]])son[u] = v;
	}
	out[u] = ++clk;
	b[clk] = u;
}
void dfs2(int u, int topfa) {
	topf[u] = topfa;
	if (!son[u])return;
	dfs2(son[u], topfa);
	for (int v : G[u]) {
		if (!topf[v])dfs2(v, v);
	}
}
int LCA(int u, int v) {
	while (topf[u] ^ topf[v]) {
		dep[topf[u]] < dep[topf[v]] ? v = fa[topf[v]] : u = fa[topf[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
int flg[N], cnt[N];
void add(int x) {
	if (!x)return;
	if (flg[x]) {
		cnt[x / S]--;
	}
	else {
		cnt[x / S]++;
	}
	flg[x] ^= 1;
}
int cal(int l, int r) {
	int bl = l / S, br = r / S;
	for (int i = l; i <= min(r, (bl + 1)*S - 1); i++) {
		if (flg[i])return i;
	}
	for (int i = bl + 1; i < br; i++) {
		if (cnt[i]) {
			for (int j = i * S; j < (i + 1)*S; j++) {
				if (flg[j])return j;
			}
		}
	}
	for (int i = max(l, br * S); i <= r; i++) {
		if (flg[i])return i;
	}
	return -1;
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for (int i = 1; i <= q; i++) {
		int u, v, l, r;
		scanf("%d%d%d%d", &u, &v, &l, &r);
		int lca = LCA(u, v);
		if (lca == u) {
			qq[i] = { 0,in[u],in[v],l,r,i };
		}
		else if (lca == v) {
			qq[i] = { 0,in[v],in[u],l,r,i };
		}
		else if (out[u] < in[v]) {
			qq[i] = { lca,out[u],in[v],l,r,i };
		}
		else {
			qq[i] = { lca,out[v],in[u],l,r,i };
		}
	}
	sort(qq + 1, qq + q + 1);
	int L = 1, R = 0;
	for (int i = 1; i <= q; i++) {
		int curl = qq[i].tl, curr = qq[i].tr;
		while (L < curl) {
			add(a[b[L++]]);
		}
		while (L > curl) {
			add(a[b[--L]]);
		}
		while (R < curr) {
			add(a[b[++R]]);
		}
		while (R > curr) {
			add(a[b[R--]]);
		}
		int lca = qq[i].lca;
		if (lca)add(a[lca]);
		ans[qq[i].id] = cal(qq[i].L, qq[i].R);
		if (lca)add(a[lca]);
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}