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 <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define fi first
#define se second
#define mpr make_pair
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i >= y; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 300010, M = 610;
struct edge{ int v, nxt; }e[N << 1];
int head[N], cnt, n, m, k, p, t, x, y, z, l, r, tot, maxx, c[N], dep[N], L[N], R[N], rev[N << 1], f[N][20], ans[N], pl[N], pr[N], pos[N], num[N], st[M][M], len[M]; bool vis[N];
struct ask{
	int idx, x, y, l, r, z;
	ask(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, int f = 0){
		idx = a; x = b; y = c; l = d; r = e; z = f;
	}
	bool operator < (const ask&rhs)const{
		return (x - 1) / t + 1 ^ (rhs.x - 1) / t + 1 ? x < rhs.x : (x - 1) / t + 1 & 1 ? y < rhs.y : y > rhs.y;
	}
}q[N];
inline void change(int x){
	x = c[rev[x]]; num[x] ^= 1;
	if(num[x]){
		int y = pos[x];
		if(!vis[x]) st[y][++len[y]] = x, vis[x] = 1;
	}
}
inline void add(int u, int v){ e[++cnt].v = v; e[cnt].nxt = head[u]; head[u] = cnt; }
inline void dfs(int u, int fa){
	dep[u] = dep[fa] + 1; f[u][0] = fa; L[u] = ++tot; rev[tot] = u;
	rep(i, 1, 18) f[u][i] = f[f[u][i - 1]][i - 1];
	repg(i, u) if(e[i].v != fa) dfs(e[i].v, u);
	R[u] = ++tot; rev[tot] = u;
}
inline int lca(int x, int y){
	if(dep[x] < dep[y]) swap(x, y); per(i, 18, 0) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	if(x == y) return x; per(i, 18, 0) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}
inline void mian(){
	n = read(); m = read(); rep(i, 1, n) c[i] = read(), maxx = max(maxx, c[i]);
	k = sqrt(maxx); p = (maxx - 1) / k + 1; rep(i, 1, maxx) pos[i] = (i - 1) / k + 1;
	rep(i, 1, p) pl[i] = (i - 1) * k + 1, pr[i] = min(maxx, i * k);
	rep(i, 1, n - 1) x = read(), y = read(), add(x, y), add(y, x); dfs(1, 0);
	rep(i, 1, m){
		x = read(); y = read(); l = read(); r = read(); r = min(r, maxx);
		if(L[x] > L[y]) swap(x, y); z = lca(x, y);
		if(R[y] <= R[x]) q[i] = ask(i, L[x], L[y], l, r, 0);
		else q[i] = ask(i, R[x], L[y], l, r, z);
	}
	t = sqrt(tot); sort(q + 1, q + m + 1); int ql = 1, qr = 0;
	rep(i, 1, m){
		int idx = q[i].idx; x = q[i].x; y = q[i].y; z = q[i].z; l = q[i].l; r = q[i].r;
		if(l > r){ ans[idx] = -1; continue; }
		while(qr < y) change(++qr); while(ql > x) change(--ql);
		while(qr > y) change(qr--); while(ql < x) change(ql++);
		if(z) change(L[z]); int bl = pos[l], br = pos[r];
		if(bl == br){
			rep(i, l, r) if(num[i]){
				ans[idx] = i; break;
			}
		}
		else{
			rep(i, l, pr[bl]) if(num[i]){
				ans[idx] = i; break;
			}
			if(!ans[idx])
			rep(i, pl[br], r) if(num[i]){
				ans[idx] = i; break;
			}
			if(!ans[idx])
			rep(i, bl + 1, br - 1){
				while(len[i] && !num[st[i][len[i]]]) vis[st[i][len[i]]] = 0, --len[i];
				if(len[i]){
					ans[idx] = st[i][len[i]]; break;
				}
			}
		}
		if(!ans[idx]) ans[idx] = -1; if(z) change(L[z]);
	}
	rep(i, 1, m) printf("%d\n", ans[i]);
}
int main(){ int qwq = 1; while(qwq--) mian(); return 0; }