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 <cmath>
#include <set>
using namespace std;

const int N = 300005, M = 300005, S = 19;

int n, m, w[N], L[N], R[N], dfn[N << 1], dfncnt;
int dep[N], fa[N][S], ans[M], cnt[N], d[N], res, pos[N << 1], t, sum[N];

int L1[N], R1[N];

int pos2[N];

bool vis[N];

int head[N], numE = 0;

set<int> s;

struct E{
	int next, v;
} e[N << 1];

void inline add(int u, int v) {
	e[++numE] = (E) { head[u], v };
	head[u] = numE;
}

void dfs(int u) {
	dfn[L[u] = ++dfncnt] = u;
	for (int i = 1; i < S && fa[u][i - 1]; i++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == fa[u][0]) continue;
		fa[v][0] = u, dep[v] = dep[u] + 1;
		dfs(v);
	}
	dfn[R[u] = ++dfncnt] = u;
}

int inline lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = S - 1; ~i; i--)
		if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
	if (x == y) return x;
	for (int i = S - 1; ~i; i--)
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

struct Q{
	int l, r, x, y, p, id;
	bool operator < (const Q &b) const {
		if (pos[l] != pos[b.l]) return l < b.l;
		return (pos[l] & 1) ? r < b.r : r > b.r;
	}
} q[M];

void inline ins(int x) {
	cnt[w[x]] ^= 1;
	if (cnt[w[x]]) sum[pos2[w[x]]]++;
	else sum[pos2[w[x]]]--;
}

int inline query(int l, int r) {
	int p = pos2[l], q = pos2[r];
	if (p == q) {
		for (int i = l; i <= r; i++)
			if (cnt[i]) return i;
	} else {
		for (int i = l; i <= R1[p]; i++)
			if (cnt[i]) return i;
		for (int i = L1[q]; i <= r; i++)
			if (cnt[i]) return i;
		for (int i = p + 1; i <= q - 1; i++) {
			if (sum[i]) {
				for (int j = L1[i]; j <= R1[i]; j++)
					if (cnt[j]) return j;
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d%d", &n, &m); t = 2 * sqrt(n);
	int rr = sqrt(n);
	for (int i = 1; i <= n; i++) scanf("%d", w + i);
	for (int i = 1; i <= 2 * n; i++) pos[i] = (i - 1) / t + 1;
	for (int i = 1; i <= n; i++) {
		pos2[i] = (i - 1) / rr + 1;
		if (!L1[pos2[i]]) L1[pos2[i]] = i;
		R1[pos2[i]] = i;
	}
	for (int i = 1, u, v; i < n; i++)
		scanf("%d%d", &u, &v), add(u, v), add(v, u);
	dfs(1);
	for (int i = 1, u, v; i <= m; i++) {
		int x, y;
		scanf("%d%d%d%d", &u, &v, &x, &y);
		if (L[u] > L[v]) swap(u, v);
		int p = lca(u, v);
		if (p == u) q[i] = (Q) { L[u], L[v], x, y, 0, i };
		else q[i] = (Q) { R[u], L[v], x, y, p, i };
	}
	sort(q + 1, q + 1 + m);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++) {
		while (l < q[i].l) ins(dfn[l++]);
		while (l > q[i].l) ins(dfn[--l]);
		while (r < q[i].r) ins(dfn[++r]);
		while (r > q[i].r) ins(dfn[r--]);
		if (q[i].p) ins(q[i].p);
		ans[q[i].id] = query(q[i].x, q[i].y);
		if (q[i].p) ins(q[i].p);
	}
	for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
	return 0;
}