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 <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

//#define int long long
//region TEMPLATE
////@formatter:off
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T&a){cin >> a;}
template<typename T,typename ... Args>void __read(T&a,Args&... args){cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); for(auto&v:(a)) cin >> v;
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
constexpr ll M7 = 1000000007;
constexpr ll M9 = 1000000009;
constexpr ll MFFT = 998244353;
constexpr double PI = 3.14159265358979323846;
template<class T> void outv(const T&a,char d=' ', bool nl=false){for(auto&x:a)cout<<x<<d;if(nl)cout<<'\n';}
static mt19937_64 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__=(ios_base::sync_with_stdio(false),cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion


int32_t main() {
    make(int, n, q);
    vector<int> a(n);
    for (auto &v : a) {
        cin >> v;
        v--;
    }
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        make(int, v, u);
        v--, u--;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    vector<int> o;
    vector<int> l_ind(n);
    vector<int> r_ind(n);
    function<void(int, int)> dfs = [&](int v, int p) {
        l_ind[v] = o.size();
        o.push_back(v);
        bool was = false;
        for (int u : g[v]) {
            if (u == p) continue;
            dfs(u, v);
            o.push_back(v);
            was = true;
        }
        if (!was) {
            o.push_back(v);
        }
        r_ind[v] = static_cast<int>(o.size()) - 1;
    };
    dfs(0, -1);
    vector<int> inc(o.size(), 1);
    for (int i = 0; i < inc.size(); ++i) {
        if (r_ind[o[i]] == i) {
            inc[i] = -max(static_cast<int>(g[o[i]].size()) - 1, 1);
        }
    }

    vector<tuple<int, int, int, int, int>> qr(q);
    for (int i = 0; i < q; ++i) {
        make(int, v, u, l, r);
        v--, u--, l--, r--;
        if (l_ind[v] > l_ind[u]) {
            swap(v, u);
        }
        if (r_ind[v] >= r_ind[u]) {
            qr[i] = {l_ind[v], l_ind[u], l, r, i};
        } else {
            int t1 = r_ind[v], t2 = l_ind[u];
            if (t1 > t2) {
                swap(t1, t2);
            }
            qr[i] = {t1, t2, l, r, i};
        }
    }

    const int D = 1400;
    sort(qr.begin(), qr.end(), [](const tuple<int, int, int, int, int> &a, const tuple<int, int, int, int, int> &b) {
        int al = get<0>(a) / D, bl = get<0>(b) / D;
        if (al != bl) return al < bl;
        if (al & 1) return get<1>(a) > get<1>(b);
        return get<1>(a) < get<1>(b);
    });

    const int Q = 500;
    vector<int> sm(n), ex(n), b((n + Q - 1) / Q);
    auto query = [&](int l, int r) {
        int bl = l / Q, br = r / Q;
        if (bl == br) {
            for (int i = l; i <= r; ++i) {
                if (ex[i]) return i;
            }
            return -2;
        }
        int en = (bl + 1) * Q;
        for (int i = l; i < en; ++i) {
            if (ex[i]) return i;
        }
        for (int bi = bl + 1; bi < br; ++bi) {
            if (b[bi] > 0) {
                int st = bi * Q;
                for (int i = 0; i < Q; ++i) {
                    if (ex[st + i]) return st + i;
                }
                assert(false);
            }
        }
        int st = br * Q;
        for (int i = st; i <= r; ++i) {
            if (ex[i]) return i;
        }
        return -2;
    };
    auto handle = [&](int i, int z) {
        int v = o[i];
        if (sm[v] != 0 && sm[v] + z != 0) {
            sm[v] += z;
            return;
        }
        int c = a[v];
        int bc = c / Q;
        b[bc] -= ex[c];
        ex[c] ^= (sm[v] != 0);
        sm[v] += z;
        ex[c] ^= (sm[v] != 0);
        b[bc] += ex[c];
    };

    vector<int> ans(q);
    int l = 0, r = -1;
    for (auto&[l1, r1, l2, r2, i] : qr) {
        while (r < r1) {
            ++r;
            handle(r, inc[r]);
        }
        while (l > l1) {
            --l;
            handle(l, inc[l]);
        }
        while (r > r1) {
            handle(r, -inc[r]);
            r--;
        }
        while (l < l1) {
            handle(l, -inc[l]);
            l++;
        }
        ans[i] = query(l2, r2) + 1;
    }

    outv(ans, '\n');

    return 0;
}