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:
#pragma GCC optimize("O3", "Ofast", "unroll-loops", "unswitch-loops", "fast-math", "no-stack-protector")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <cstring>
#include <cassert>
#include <string>
#include <unordered_set>

using namespace std;

const int mx_MEM = 7 * 1e7;
int mpos = 0;
char mem[mx_MEM];

inline void *operator new(size_t n) {
    assert((mpos += n) <= mx_MEM);
    return (void *) (mem + mpos - n);
}

inline void operator delete(void *) noexcept {}

//#define MULTITEST

//#define int long long
const int SZ = 3e5 + 4;
const int inf = 2e18;
const int mod = 1e9 + 7;

int n, q;
int a[SZ];
vector<int> g[SZ];

void read() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
}

int p[20][SZ];
int tin[SZ];
int tout[SZ];
int tim = 0;
vector<int> v;

void dfs(int u, int par = -1) {
    tin[u] = tim++;
    v.push_back(u);
    p[0][u] = par;
    for (int v : g[u]) {
        if (v == par) continue;
        dfs(v, u);
    }
    tout[u] = tim++;
    v.push_back(u);
}

bool is_ancestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) {
        return u;
    }
    if (is_ancestor(v, u)) {
        return v;
    }

    for (int k = 19; k >= 0; --k) {
        if (p[k][v] == -1) continue;
        if (is_ancestor(p[k][v], u)) continue;
        v = p[k][v];
    }

    return p[0][v];
}

struct query {
    int l, r, l1, r1, u, i;
};

const int k = 1900;
const int k2 = 666;
bool cnt[SZ];
bool col[SZ];
int b[SZ / k2 + 1];

void chCol(int c) {
    if (col[c]) {
        --b[c / k2];
    }
    col[c] ^= true;
    if (col[c]) {
        ++b[c / k2];
    }
}

void ch(int u) {
    if (cnt[u]) {
        chCol(a[u]);
    }
    cnt[u] ^= true;
    if (cnt[u]) {
        chCol(a[u]);
    }
}

int get(int l, int r) {
    for (int i = l; i <= r;) {
        if (i % k2 == 0 && i + k2 - 1 <= r) {
            if (b[i / k2]) {
                for (int j = 0; j < k2; ++j) {
                    if (col[i + j] & 1) return i + j;
                }
                assert(false);
            }
            i += k2;
        } else {
            if (col[i] & 1) return i;
            ++i;
        }
    }
    return -1;
}

void solve() {
    memset(p, 255, sizeof p);
    dfs(0);

    for (int j = 1; j < 20; ++j) {
        for (int i = 0; i < n; ++i) {
            if (p[j - 1][i] == -1) continue;
            p[j][i] = p[j - 1][p[j - 1][i]];
        }
    }

    vector<query> x;
    for (int i = 0; i < q; ++i) {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        --u, --v;

        if (tin[u] > tin[v]) swap(u, v);

        if (is_ancestor(u, v)) {
            x.push_back({tin[u], tin[v], l, r, -1, i});
        } else {
            int w = lca(u, v);
            x.push_back({tout[u], tin[v], l, r, w, i});
        }
    }

    sort(x.begin(), x.end(), [&](const query& a, const query& b) {
        if (a.l / k < b.l / k) return true;
        if (b.l / k < a.l / k) return false;

        if ((a.l / k) & 1) {
            return a.r < b.r;
        } else {
            return a.r > b.r;
        }
    });

    int l = 0, r = -1;
    vector<int> ans(q);
    for (int i = 0; i < q; ++i) {
        while (l < x[i].l) {
            ch(v[l]);
            ++l;
        }
        while (l > x[i].l) {
            --l;
            ch(v[l]);
        }
        while (r < x[i].r) {
            ++r;
            ch(v[r]);
        }
        while (r > x[i].r) {
            ch(v[r]);
            --r;
        }

        if (x[i].u != -1) {
            chCol(a[x[i].u]);
        }
        ans[x[i].i] = get(x[i].l1, x[i].r1);
        if (x[i].u != -1) {
            chCol(a[x[i].u]);
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t;

#ifdef MULTITEST
    cin >> t;
#else
    t = 1;
#endif

    for (int i = 0; i < t; ++i) {
        read();
        solve();
    }

    return 0;
}