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 maxn 600086

using namespace std;

int n, m, sn;
vector<int> v[maxn];
int x, y, l, r;
int eu[maxn], st[maxn], ed[maxn], cnt;
int fa[maxn][25], lg[maxn], dep[maxn];

void dfs(int i){
	eu[st[i] = ++cnt] = i, dep[i] = dep[fa[i][0]] + 1;
	for(int j = 1;j <= 20;j++) fa[i][j] = fa[fa[i][j - 1]][j - 1];
	for(int j = 0;j < v[i].size();j++){
		int to = v[i][j];
		if(to == fa[i][0]) continue;
		fa[to][0] = i;
		dfs(to);
	}
	eu[ed[i] = ++cnt] = i;
}

inline int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]]];
	if(x == y) return x;
	for(int i = 20;~i;i--) if(fa[x][i] ^ fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

struct query{
	int l, r, pos, i, lca, L, R;
}q[maxn];

inline bool cmp(query x, query y){
	return x.pos ^ y.pos ? x.pos < y.pos : x.pos & 1 ? x.r < y.r : x.r > y.r;
}

int a[maxn], ans[maxn];
bool tag[600][600];
int tot[maxn];

void modify(int x){
	int id = a[x] / sn;
	tag[id][a[x] - id * sn] ^= 1;
	if(tag[id][a[x] - id * sn]) tot[id]++;
	else tot[id]--;
}

int main(){
	scanf("%d%d", &n, &m);
	sn = (int)sqrt(n << 1);
	for(int i = 2;i <= n;i++) lg[i] = lg[i >> 1] + 1;
	for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
	for(int i = 1;i < n;i++){
		scanf("%d%d", &x, &y);
		v[x].push_back(y), v[y].push_back(x);
	}
	dfs(1);
	for(int i = 1;i <= m;i++){
		scanf("%d%d%d%d", &x, &y, &l, &r);
		if(st[x] > st[y]) swap(x, y);
		if(ed[x] >= ed[y]) q[i] = (query){st[x], st[y], st[x] / sn + 1, i, 0, l, r};
		else q[i] = (query){ed[x], st[y], ed[x] / sn + 1, i, lca(x, y), l, r};
	}
	sort(q + 1, q + 1 + m, cmp);
	int l = 1, r = 1;
	sn = (int)sqrt(n), modify(eu[1]);
	memset(ans, -1, sizeof(ans));
	for(int i = 1;i <= m;i++){
		while(l > q[i].l) modify(eu[--l]);
		while(r < q[i].r) modify(eu[++r]);
		while(l < q[i].l) modify(eu[l++]);
		while(r > q[i].r) modify(eu[r--]);
		if(q[i].lca) modify(q[i].lca);
		int L = q[i].L / sn, R = q[i].R / sn;
		if(L == R){
			for(int j = q[i].L;j <= q[i].R && ans[q[i].i] == -1;j++){
				if(tag[L][j - L * sn]) ans[q[i].i] = j;
			}
		}else{
			for(int j = q[i].L;j / sn == L && ans[q[i].i] == -1;j++){
				if(tag[L][j - L * sn]) ans[q[i].i] = j;
			}
			for(int j = q[i].R;j / sn == R && ans[q[i].i] == -1;j--){
				if(tag[R][j - R * sn]) ans[q[i].i] = j;
			}
			for(int j = L + 1;j < R && ans[q[i].i] == -1;j++){
				if(!tot[j]) continue;
				for(int k = j * sn;k / sn == j && ans[q[i].i] == -1;k++){
					if(tag[j][k - j * sn]) ans[q[i].i] = k;
				}
			}
		}
		if(q[i].lca) modify(q[i].lca);
	}
	for(int i = 1;i <= m;i++) printf("%d\n", ans[i]);
}