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 <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <fstream>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define x first
#define y second
#define Time (double)clock()/CLOCKS_PER_SEC
#define debug(x) std::cerr << #x << ": " << x << '\n';
#define FOR(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define trav(a, x) for (auto& a : x)
using vi = vector<int>;
template <typename T>
std::ostream& operator <<(std::ostream& output, const pair <T, T> & data)
{
    output << "(" << data.x << "," << data.y << ")";
    return output;
}
template <typename T>
std::ostream& operator <<(std::ostream& output, const std::vector<T>& data)
{
    for (const T& x : data)
        output << x << " ";
    return output;
}
ll div_up(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll div_down(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down 
ll math_mod(ll a, ll b) { return a - b * div_down(a, b); }
#define tcT template<class T
#define tcTU tcT, class U
tcT> using V = vector<T>; 
tcT> void re(V<T>& x) { 
    trav(a, x)
        cin >> a;
}
tcT> bool ckmin(T& a, const T& b) {
    return b < a ? a = b, 1 : 0; 
} // set a = min(a,b)
tcT> bool ckmax(T& a, const T& b) {
    return a < b ? a = b, 1 : 0; 
}
ll gcd(ll a, ll b) {
    while (b) {
        tie(a, b) = mp(b, a % b);
    }
    return a;
}

const int N = 6e5+7;

namespace Tree {
vi g[N];
const int LG = 20;
int ptr = 0, to[N][LG], h[N], l[N], r[N];
void calc(int u, int p) {
    to[u][0] = p;
    for (int i = 1; i < LG; ++i)
        to[u][i] = to[to[u][i-1]][i-1];
    l[u] = ptr;
    ptr++;    
    for (int v : g[u])  
        if (v != p) {
            h[v] = h[u]+1;
            calc(v, u);
        }
   r[u] = ptr - 1;
}   
bool anc(int u, int v) { return l[u] <= l[v] && r[v] <= r[u]; }
int lca(int u, int v) {
    if (anc(u,v))   
        return u;
    for (int i = LG - 1; i >= 0; --i)
        if (!anc(to[u][i], v))
            u = to[u][i];
    return to[u][0];
}   
int dist(int u, int v) { return h[u] + h[v] - 2 * h[lca(u,v)]; }
};

mt19937_64 rnd(2007);
ll val[N];
int a[N];
vi d[N];
vi vert[N];
vi want[N];

int type[N]; // 0 - dk, 1 - exist, -1 - doesnt exist
int L[N], R[N];
int sum[N];

struct Fen {
ll f[N];
void clear() {
    for (int i = 0; i < N; ++i) f[i] = 0;
}   
void add(int i, int x) {
    for (; i < N; i |= i + 1) 
        f[i] ^= x;
}   
void add(int l, int r, int x) {
    add(l, x);
    add(r + 1, x);
}
int get(int i) {
    int ans = 0;
    for (; i >= 0; i &= i + 1, --i) ans ^= f[i];
    return ans;
}   
} f;

signed main() {
	#ifdef ONLINE_JUDGE
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    FOR (i, N)
    	val[i] = rnd();

    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
    	cin >> a[i];
    	vert[a[i]].app(i);
    }

    FOR (i, n - 1) {
    	int u, v;
    	cin >> u >> v;
    	Tree::g[u].app(v);
    	Tree::g[v].app(u);
    	//read tree
    }

    //precalc for lca
    Tree::calc(1, 1);
    int ptr = 0;
    FOR (i, q) {
    	d[i].resize(4);
    	re(d[i]);
    	d[i].app(Tree::lca(d[i][0], d[i][1]));
    	tie(L[i], R[i]) = mp(d[i][2], d[i][3]);
    }

    FOR (it, 21) {
    	FOR (i, N) {
    		want[i].clear();
    		sum[i] = 0;
    	}
    	FOR (i, q) {
            if (type[i] == -1 || (type[i] && L[i] == R[i]))
                continue;

			int u = d[i][0], v = d[i][1];
			auto add = [&] (int l, int r) {
				want[l - 1].app(i);
				want[r].app(i);
			};
			if (type[i] == 0) {
				add(L[i], R[i]);
			}
			else if (L[i] < R[i]) {
				int m = (L[i] + R[i]) / 2;
				add(L[i], m);
			}
    	}
        f.clear();
    	for (int x = 1; x <= n; ++x) {
    		trav (u, vert[x])
    			f.add(Tree::l[u], Tree::r[u], val[a[u]]);
    		trav (i, want[x]) {
    			int u = d[i][0], v = d[i][1];
    			sum[i] ^= f.get(Tree::l[u]) ^ f.get(Tree::l[v]);
    		}
    	}
    	FOR (i, q) {
            if (type[i] == -1 || (type[i] && L[i] == R[i]))
                continue;

			int lc = d[i][4];

			int l = L[i], r;
			if (type[i] == 0)
				r = R[i];
			else
				r = (L[i] + R[i]) / 2;

			if (L[i] <= a[lc] && a[lc] <= r)
				sum[i] ^= val[a[lc]];

			if (type[i] == 0) {
				if (sum[i] == 0)
					type[i] = -1;
				else
					type[i] = 1;
			}
			else {
				if (sum[i] == 0)
					L[i] = r + 1;
				else
					R[i] = r;
			}
    	}
    }

    FOR (i, q) {
    	if (type[i] == -1) {
    		cout << -1 << endl;
        }
    	else {
    		assert(L[i] == R[i]);
    		cout << L[i] << endl;
    	}
    }
}