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 DEBUG
#include "../../debug.h"
#else
#define DEB(...)
#endif
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define sz(a) ((int)(a).size())
#define forn(i,n) for(int i=0; i<(n); i++)
#define forne(i,n) for(int i=0; i<(n) || (cout << endl,0) ; i++) 
#define fora(i,a,b) for(int i=a; i<=(b); i++)
#define ford(i,a,b) for(int i=a; i>=(b); i--)
#define endl '\n'
#define muniq(x) sort(all(x)), x.erase(unique(all(x)), x.end())
template<class T> bool mmin(T& a, const T& b) { return b<a?a=b,1:0; }
template<class T> bool mmax(T& a, const T& b) { return a<b?a=b,1:0; }
template<class T> void puts(T a) { cout << a << ' '; }
template<class T> void put(T a) { cout << a << endl; }
template<class T> void put(T ita, T itb) { while(ita!=itb) puts(*ita++); cout << endl; }
void yesno(bool c) { put(c?"YES":"NO"); }
void yes() { yesno(true); } void no() { yesno(false); }
void imp() { put("-1"); }
const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3f;

// -------------------------------------

struct base_graph {
    int n, ecnt = 0;
    vector<int> from,to;

    base_graph(int n) : n(n) {}

    void reserve(int m) {
        from.reserve(m);
        to.reserve(m);
    }

    virtual int add(int a, int b) {
        assert(0 <= a && a < n);
        assert(0 <= b && b < n);
        from.push_back(a); to.push_back(b);
        return ecnt++;
    }
};

struct dir_graph : public base_graph {
    vector<vector<pair<int,int>>> out,in;

    dir_graph(int n) : base_graph(n), out(n), in(n) {}

    int add(int a, int b) {
        int e = base_graph::add(a,b);
        out[a].push_back({e,b});
        in[b].push_back({e,a});
        return e;
    }
};

struct undir_graph : public base_graph {
    vector<vector<pair<int,int>>> edg;

    undir_graph(int n) : base_graph(n), edg(n) {}

    int add(int a, int b)  {
        if(b>a) swap(a,b);
        int e = base_graph::add(a,b);
        edg[a].push_back({e,b});
        edg[b].push_back({e,a});
        return e;
    }
};

// -------------------------------------

template<class T, class G> 
struct weightable : public G {
    vector<T> w;

    weightable(int n) : G(n) {}

    using G::add;

    int add(int a, int b, T ww) {
        w.push_back(ww);
        return G::add(a,b);
    }

    void reserve(int m) {
        G::reserve(m);
        w.reserve(m);
    }
};

template<class T> using wdir_graph = weightable<T,dir_graph>;
template<class T> using wundir_graph = weightable<T,undir_graph>;

// -------------------------------------

void readin(base_graph& g, int m, int offset = 1) {
    g.reserve(m);
    for(int i=0; i<m; i++) {
        int a, b;
        cin >> a >> b;
        a -= offset;
        b -= offset;
        g.add(a,b);
    }
}

template<class T, class G>
void readinw(weightable<T,G>& g, int m, int offset = 1) {
    g.reserve(m);
    for(int i=0; i<m; i++) {
        int a, b; T ww = 0;
        cin >> a >> b >> ww;
        a -= offset;
        b -= offset;
        g.add(a,b,ww);
    }
}

void readin_tree_format(base_graph& g, int offset = 1) {
    int m = g.n-1;
    g.reserve(m);
    for(int i=2; i<=m; i++) {
        int p; cin >> p;
        int a = i-offset;
        g.add(a,p);
    }
}

// ---------------------------------------------


// ---------------------------------------------

struct binary_lifting {
    const int mxw = 20;
    vector<int> dep;
    vector<vector<int>> par;

    binary_lifting(undir_graph& g) : dep(g.n), par(g.n,vector<int>(mxw,-1)) {  // assumes 0-index of nodes
        function<void(int,int,int)> dfs = [&](int u, int p, int d) {
            dep[u] = d;

            int pp = p;
            for(int k=0; k<mxw && pp>=0; k++) {
                par[u][k] = pp;
                pp = par[pp][k];
            }

            for(auto [e,v] : g.edg[u]) 
                if(v!=p) dfs(v,u,d+1);
        };
        dfs(0,-1,0);
//        forn(i,g.n) forne(j,mxw) puts(par[i][j]) ;
    }

// -----------------------------------

    int fast_bin_search(int u, bool (*f)(int v)) {
        for(int i=mxw-1; i>=0; i--) {
            if(par[u][i] && f(par[u][i]))
                u = par[u][i];
        }

        // nodes (not) fulfilling criterion on path in tree:       
        //         <- root   ...   leaf ->
        // ...   par[u][0]    |   u             ...
        // ...   !f           |   f     ...

        return u;
    }

// -----------------------------------

    int walkup(int u, int h) {
        assert(h<=dep[u]);

        int i = 0;
        while(h) {
            if(h&1) u = par[u][i];    // i++ in if ?  TEST
            i++;
            h = h>>1;
        }
        return u;
    }

    int lca(int a, int b) {
        DEB(a,b);
        if(dep[a]<dep[b])
            swap(a,b);
        a = walkup(a,dep[a]-dep[b]);

        DEB(a,b);
        if(a==b) return a;

        // fast binary search
        for(int i=mxw-1; i>=0; i--) {
            if(par[a][i]!=par[b][i]) {
                a = par[a][i];
                b = par[b][i];
            }
        }

        return par[a][0];
    }
};

// ---------------------------------------------
// ----------------------------------------------

template <class S, S (*op)(S, S), S (*e)()> 
struct pers_segtree {
  public:
    pers_segtree() : pers_segtree(0) {}
    pers_segtree(int n) : pers_segtree(std::vector<S>(n, e())) {}
    pers_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = 1, log = 0, _ver = 0;
        while(size<_n) log++, size <<= 1;
        d = std::vector<vector<_node>>(2 * size,vector<_node>(1,{0,0,e()}));
//        fill(d.begin()+size,d.end(),vector<_node>(1,{0,0,e()}));
        for(int i=0; i<_n; i++) d[i+size][0].s = v[i];
    }

    void build() {
        assert(!is_built);
        is_built = true;
        for (int i = size - 1; i >= 1; i--) pull(i);
    }

    S& operator[] (int p) {
        assert(0 <= p && p < _n);
        assert(!is_built);
        return d[p+size][0].s;
    }

    S get_latest(int p) {
        assert(0 <= p && p < _n);
        return d[p+size].back().s;
    }

    int update(int ver, int p, const S s) {
        assert(0 <= p && p < _n);
        assert(is_built);
        assert(0 <= ver && ver <= _ver);
        p += size;
//        int it = ver;
//        stack<int> stl,str;
//        stack<int> st;
        d[1].push_back(d[1][ver]);
//        return 0;
        for (int i = log - 1; i >= 0; i--) {
//            if(it>=d[p>>i].size()) {
//                cout << p << " " << i << " " << (p>>i) << " " << d[p>>i].size() << " " << it << endl;
//                assert(false);
//            }
//            if((p>>i)>1) {
//                if((p>>i) & 1) d[p>>(i+1)].back().itr = d[p>>i].size();
//                else d[p>>(i+1)].back().itl = d[p>>i].size();
//            }
            int& it = ((p>>i) & 1) ? d[p>>(i+1)].back().itr : d[p>>(i+1)].back().itl;
            d[p>>i].push_back(d[p>>i][it]);
            it = d[p>>i].size() - 1;

//            it = d[p>>i].size();
//            st.push(it);
//            int itl = d[p>>i][it].itl, itr = d[p>>i][it].itr;
//            int it = d[p>>(i-1)].size();
//
//            if((p >> (i-1)) & 1) {
//                d[p>>(i-1)]
//
//            stl.push(itl);
//            str.push(itr);
        }
        d[p].back().s = s;
        for (int i = 1; i <= log; i++) {
            pull(p >> i);
        }
        return ++_ver;
    }

    S query(int ver, int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        assert(0 <= ver && ver <= _ver);
        assert(is_built);
        if (l == r) return e();
        return query(1, ver, l, r, 0, size);
    }

    S queryall(int ver) { 
        assert(0 <= ver && ver <= _ver);
        assert(is_built);
        return d[1][ver].s; 
    }
/*
    // to be implemented for persistent segtree
    template <void (*f)(S)> void query_unary(int ver, int l, int r) {
        return query_unary(ver, l, r, [](S x) { return f(x); });
    }
    template <class F> void query_unary(int ver, int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        assert(0 <= ver && ver <= _ver);
        assert(is_built);
        if(l==r) return;
        l += size;
        r += size;
        int itl = 0, itr = 0;

        while (l < r) {
            if (l & 1) {
                itl = next_dver_iter(itl, l, ver);
                f(d[l++][itl]);
            }
            if (r & 1) {
                itr = next_dver_iter(itr, r-1, ver);
                f(d[--r][itr]);
            }
            l >>= 1;
            r >>= 1;
        }
    }
*/

    // to be implemented for persistent segtree
    // returns maximal r, s.t. f(query(l,r))==true
    template <bool (*f)(S)> int max_right(int ver, int l) {
        return max_right(ver, l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int ver, int l, F f) {
        assert(0 <= l && l <= _n);
        assert(0 <= ver && ver <= _ver);
        assert(is_built);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;

        int it = ver;
        stack<int> its;
        its.push(it);
        for (int i = log; i >= 1; i--) {
            int nit = d[l>>i][it].itl;
            if((l >> (i-1)) & 1) nit = d[l>>i][it].itr;
            its.push(nit);
            it = nit;
        }

        S sm = e();
        do {
            auto repair_its = [&]() {
                its.pop();
                if(l==1) its.push(ver); 
                else its.push(d[l>>1][its.top()].itr);
            };

            while (l % 2 == 0) l >>= 1, its.pop();
            repair_its();
            
            if (!f(op(sm, d[l][its.top()].s))) {
                while (l < size) {
                    its.push(d[l][its.top()].itl);
                    l = (2 * l);
                    if (f(op(sm, d[l][its.top()].s))) {
                        sm = op(sm, d[l][its.top()].s);
                        l++;
                        repair_its();
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l][its.top()].s);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <class F> int max_right2(vector<int> ver, int l, F f) {
        assert(0 <= l && l <= _n);
        int nver = ver.size();
        assert(nver>=1);
        forn(i,nver) assert(0 <= ver[i] && ver[i] <= _ver);
        assert(is_built);
//        assert(f(e()));
        if (l == _n) return _n;
        l += size;

        vector<stack<int>> its(nver);
DEB(l,log);
        auto prep_its = [&](stack<int>& its, int ver) {
            int it = ver;
            its.push(it);
            for (int i = log; i >= 1; i--) {
//                DEB(l>>i,it);
//                return;
                int nit = d[l>>i][it].itl;
                if((l >> (i-1)) & 1) nit = d[l>>i][it].itr;
                its.push(nit);
                it = nit;
            }
        };
        forn(i,nver) prep_its(its[i],ver[i]);
//return 0;
        vector<S> sm(nver,e());
        do {
            auto repair_its = [&](int i) {
                if(l>1) {
                    its[i].pop();
                    its[i].push(d[l>>1][its[i].top()].itr);
                }
            };

            while (l % 2 == 0) {
                l >>= 1;
                forn(i,nver) its[i].pop();
            }
            forn(i,nver) repair_its(i);
DEB(l);            
            vector<S> opres(nver);
            forn(i,nver) DEB(its[i].top(),d[l][its[i].top()].s.val);;
            forn(i,nver) opres[i] = op(sm[i],d[l][its[i].top()].s);
            if (!f(opres)) {
DEB(l,size);
                while (l < size) {
                    forn(i,nver) its[i].push(d[l][its[i].top()].itl);
                    l = (2 * l);
DEB(l);            
                    forn(i,nver) opres[i] = op(sm[i],d[l][its[i].top()].s);
                    if (f(opres)) {
                        forn(i,nver) sm[i] = op(sm[i],d[l][its[i].top()].s);
                        l++;
                        forn(i,nver) repair_its(i);
                    }
                }
                return l - size;
            }
            forn(i,nver) sm[i] = op(sm[i],d[l][its[i].top()].s);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

/*
    // to be implemented for persistent segtree
    // returns minimal l, s.t. f(query(l,r))==true
    template <bool (*f)(S)> int min_left(int ver, int r) {
        return min_left(ver, r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int ver, int r, F f) {
        assert(0 <= r && r <= _n);
        assert(0 <= ver && ver <= _ver);
        assert(is_built);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        int itr = 0;
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            itr = next_dver_iter(itr, r, ver);
            if (!f(op(d[r][itr], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    itr = next_dver_iter(itr, r, ver);
                    if (f(op(d[r][itr], sm))) {
                        sm = op(d[r][itr], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r][itr], sm);
        } while ((r & -r) != r);
        return 0;
    }
*/
  private:
    struct _node {
        int itl, itr;
        S s;
    };

    int _n, size, log, _ver;
    bool is_built = false;
    std::vector<vector<_node>> d;

    void pull(int k) { //int itl, int itr) {
        _node& target = d[k].back();
        DEB(target.itl, target.itr);
//        return;
        target.s = op(d[2 * k][target.itl].s,d[2 * k + 1][target.itr].s);
    }

    S query(int k, int it, int l, int r, int u, int v) {
        if(l<=u && v<=r) return d[k][it].s;
        int mid = (u+v) / 2;
        S sm = e();
        if(l<mid) sm = op(sm,query(k<<1, d[k][it].itl, l, r, u, mid));
        if(mid<r) sm = op(sm,query(k<<1|1, d[k][it].itr, l, r, mid, v));
        return sm;
    }

};

// ----------------------------------------------

namespace xorseg {
    struct node {
        ll val;
        node() : val(0) {}
        node(ll a) : val(a) {}
    };
    node op(node lhs, node rhs) { return node(lhs.val ^ rhs.val); }
    node e() { return node(0); }
    using seg = pers_segtree<node,op,e>;
}
using namespace xorseg;

// -----------------------------------

// ---------------------------------------

struct randll {
    mt19937 rng;
    uniform_int_distribution<long long> rg;

    randll(long long from, long long to) : rng(std::chrono::high_resolution_clock::now().time_since_epoch().count()), rg(from,to) {}

    long long getll() {
        return rg(rng);
    }
};

// ---------------------------------------

void solve() {
    int n,q; cin >> n >> q;
    vi a(n);
    forn(i,n) cin >> a[i];

    undir_graph g(n);
    readin(g,n-1);

    vi uq(q),vq(q),lq(q),rq(q);
    forn(i,q) cin >> uq[i] >> vq[i] >> lq[i] >> rq[i];
    forn(i,q) {
        uq[i]--;
        vq[i]--;
    }

    binary_lifting bin(g);              // improve repertoire
    randll ran(0,infl);
    vl fp(n+1), curfp(n+1);
    fora(i,1,n) fp[i] = ran.getll();

    seg tree(n+1);
    tree.build();
//return;
    vi ver(n), par(n);
//    unordered_map<long long,int> seen;
    function<void(int,int)> dfs = [&](int u, int p) {
        par[u] = p;
//        ll val = seen[fp[a[u]]] ? 0 : fp[a[u]];
//        seen[fp[a[u]]] ^= 1;
        curfp[a[u]] ^= fp[a[u]];
        ver[u] = tree.update(p==-1?0:ver[p],a[u],curfp[a[u]]);
        for(auto [e,v] : g.edg[u]) {
            if(v==p) continue;
            dfs(v,u);
        }
        curfp[a[u]] ^= fp[a[u]];
//        seen[fp[a[u]]] ^= 1;
    };

    dfs(0,-1);
//    return;

    forn(i,q) {
        int lca = bin.lca(uq[i],vq[i]);
DEB(lca);
        auto func = [&](vector<node> sm) {
            ll val = 0;
            int nver = sm.size();
            forn(i,nver) DEB(sm[i].val);
            forn(i,nver) val ^= sm[i].val;
            DEB(val);
            return val==0;
        };

        vi vers = { ver[uq[i]], ver[vq[i]], ver[lca]};
        if(lca>0) vers.push_back(ver[par[lca]]);
        int r = tree.max_right2(vers, lq[i], func);
DEB(rq[i],r);
        if(rq[i] < r) imp();
        else put(r);
    }
    /*
    */
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tc = 1; //cin >> tc;
    while(tc--) solve();

    return 0;
}