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;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 300000, logN = 18, M = 2e7;

struct Seg {
    int l, r, m, x, y, hash, hash2;
    Seg* ch[2];
    Seg() = default;
    Seg (int _l, int _r) : l(_l), r(_r), m(l + r >> 1), x(rand()), y(rand()) {
        if (r - l > 1) {
            ch[0] = new Seg(l, m);
            ch[1] = new Seg(m, r);
            pull();
        } else {
            hash = hash2 = 0;
        }
    }
    Seg (Seg* i) : l(i->l), r(i->r), m(i->m), x(i->x), y(i->y), hash(i->hash), ch{i->ch[0], i->ch[1]} {}
    void pull() {
        hash = (1ll * ch[0]->hash * x + 1ll * ch[1]->hash * y) % mod;
        hash2 = (1ll * ch[0]->hash2 * y + 1ll * ch[1]->hash2 * x) % mod;
    }
    Seg* modify(int p, int v) {
        Seg *cur = new Seg(this);
        if (r - l == 1) {
            cur->hash = cur->hash2 = v;
        } else {
            cur->ch[p >= m] = cur->ch[p >= m]->modify(p, v);
            cur->pull();
        }
        return cur;
    }
    int query(int p) {
        if (r - l == 1) return hash;
        return ch[p >= m]->query(p);
    }
};

vector <int> adj[N];
int in[N], out[N], _id = 0, jump[N][logN];
vector <int> order;
vector <Seg*> roots;

void dfs(int v, int pa) {
    in[v] = _id++;
    jump[v][0] = pa;
    order.pb(v);
    for (int u : adj[v]) if (u != pa) {
        dfs(u, v);
    }
    out[v] = _id++;
    order.pb(v);
}

void build() {
    for (int j = 0; j < logN; ++j) for (int i = 0; i < N; ++i) jump[i][j] = -1;
    dfs(0, -1);
    for (int j = 1; j < logN; ++j) {
        for (int i = 0; i < N; ++i) {
            int k = jump[i][j - 1];
            if (k == -1) continue;
            jump[i][j] = jump[k][j - 1];
        }
    }
}

bool anc(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}

int lca(int u, int v) {
    if (anc(u, v)) return u;
    if (anc(v, u)) return v;
    for (int i = logN - 1; ~i; --i) {
        int k = jump[u][i];
        if (~k && !anc(k, v)) u = k;
    }
    return jump[u][0];
}

int get(Seg* l, Seg* r, int tl, int tr) {
    if (tr - tl == 1) return tl;
    int tm = tl + tr >> 1;
    if (l->ch[0]->hash != r->ch[0]->hash || l->ch[0]->hash2 != r->ch[0]->hash2) return get(l->ch[0], r->ch[0], tl, tm);
    return get(l->ch[1], r->ch[1], tm, tr);
}

int query(Seg* l, Seg* r, int a, int b, int tl, int tr) {
    int tm = tl + tr >> 1;
    if (a <= tl && tr <= b) {
        if (l->hash == r->hash && l->hash2 == r->hash2) return -2;
        return get(l, r, tl, tr);
    }
    if (a < tm) {
        int t = query(l->ch[0], r->ch[0], a, b, tl, tm);
        if (t != -2) return t;
    }
    if (tm < b) {
        int t = query(l->ch[1], r->ch[1], a, b, tm, tr);
        if (t != -2) return t;
    }
    return -2;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    srand(time(NULL));
    int n, q;
    cin >> n >> q;
    vector <int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i], --a[i];
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    build();
    roots.pb(new Seg(0, n));
    vector <int> cnt(n, 0);
    for (int i : order) {
        cnt[a[i]] ^= 1;
        roots.pb(roots.back()->modify(a[i], cnt[a[i]]));
    }
    while (q--) {
        int u, v, l, r;
        cin >> u >> v >> l >> r, --u, --v, --l;
        int k = lca(u, v);
        if (k == u || k == v) {
            if (k == v) swap(u, v);
            int x = in[u], y = in[v];
            cout << query(roots[x], roots[y + 1], l, r, 0, n) + 1 << '\n';
        } else {
            int x = out[u], y = in[v];
            if (x > y) x = out[v], y = in[u];
            Seg* tmp = roots[y + 1]->modify(a[k], roots[y + 1]->query(a[k]) ^ 1);
            cout << query(roots[x], tmp, l, r, 0, n) + 1 << '\n';
        }
    }
}