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>

using namespace std;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

struct union_find
{
	vector<int> p;

	union_find(int n = 0) : p(n, -1) {}

	bool join(int u, int v)
	{
		if ((u = root(u)) == (v = root(v)))
			return false;
		if (p[u] > p[v])
			swap(u, v);
		p[u] += p[v];
		p[v] = u;
		return true;
	}

	int root(int u) { return p[u] < 0 ? u : p[u] = root(p[u]); }
};

int main()
{
	#ifdef TurnRed
		freopen("a.in", "r", stdin);
		//freopen("a.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for (auto &i : a) cin >> i, --i;

	vector<vector<int>> adj(n);
	for (int i = 1, u, v; i < n; ++i)
	{
		cin >> u >> v;
		--u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	struct info { int u, v, l, r, lca, id; };
	vector<info> queries(q);
	for (auto &i : queries)
	{
		cin >> i.u >> i.v >> i.l >> i.r;
		--i.u, --i.v, --i.l, --i.r;
		i.id = &i - &queries[0];
	}

	vector<int> ancestor(n, -1);
	vector<vector<int>> who(n);
	union_find uf(n);
	for (auto &i : queries)
		who[i.u].push_back(&i-&queries[0]),
		who[i.v].push_back(&i-&queries[0]);

	vector<int> ft(n), ord;
	function<void(int)> dfs = [&](int u)
	{
		ord.push_back(a[u]);
		ancestor[u] = u;
		for (auto v : adj[u])
			if (ancestor[v] == -1)
			{
				dfs(v);
				uf.join(u, v);
				ancestor[uf.root(u)] = u;
			}
		for (auto i : who[u])
		{
			int v = u ^ queries[i].v ^ queries[i].u;
			if (ancestor[v] != -1)
				queries[i].lca = ancestor[uf.root(v)];
		}
		ft[u] = ord.size();
		ord.push_back(a[u]);
	};
	dfs(0);

	for (auto &i : queries)
	{
		i.u = ft[i.u], i.v = ft[i.v], i.lca = ft[i.lca];
		if (i.u > i.v) swap(i.u, i.v);
	}

	const int R = 280, R2 = 1100;
	sort(queries.begin(), queries.end(), [](const info &x, const info &y) -> bool
	{
		if (x.u / R2 != y.u / R2)
			return x.u < y.u;
		return (x.v < y.v) ^ (x.u / R2 & 1);
	});

	vector<unsigned short> b(n / R + 1);
	vector<char> cur(n);

	auto upd = [&](int p)
	{
		p = ord[p];
		b[p / R] -= cur[p];
		cur[p] ^= 1;
		b[p / R] += cur[p];
	};

	auto walk = [&](int l, int r, int &ans)
	{
		for (; l <= r; ++l)
			if (cur[l])
			{
				ans = l + 1;
				break;
			}
	};

	int l = 0, r = 0;
	vector<int> vans(q);
	for (auto &i : queries)
	{
		while (l < i.u) upd(l++);
		while (l > i.u) upd(--l);
		while (r < i.v) upd(r++);
		while (r > i.v) upd(--r);
		upd(i.lca);

		int bl = i.l / R, br = i.r / R, ans = -1;
		if (bl * R != i.l)
		{
			walk(i.l, min(i.r, ++bl * R - 1), ans);
			i.l = bl * R;
		}
		if (i.l <= i.r && i.r + 1 != (br + 1) * R)
			walk(br-- * R, i.r, ans);

		for (; bl <= br; ++bl)
			if (b[bl])
			{
				walk(bl * R, (bl + 1) * R, ans);
				break;
			}
		vans[i.id] = ans;
		upd(i.lca);
	}

	for (auto &i : vans)
		cout << i << "\n";

	return 0;
}