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 <iomanip>
#include <cstdio>
#include <vector>
#include <bitset>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <algorithm>
#include <random>
#include <cmath>
#include <cassert>
#include <climits>
#include <ctime>
#include <chrono>



#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")



#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << x << endl;
#else
    #define dbg(x)
#endif

#define pb push_back
#define ppb pop_back()
#define mp make_pair
#define fi(a, b) for (int i = a; i < b; i++)
#define fj(a, b) for (int j = a; j < b; j++)
#define fk(a, b) for (int k = a; k < b; k++)
#define fi1(a, b) for (int i = a - 1; i >= b; i--)
#define fj1(a, b) for (int j = a - 1; j >= b; j--)
#define fk1(a, b) for (int k = a - 1; k >= b; k--)
#define fx(x, a) for (auto& x : a)
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define rep1(i, a, b) for (int i = a - 1; i >= b; --i)
#define siz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

using namespace std;

template<typename T1, typename T2>inline void mine(T1 &x, const T2 &y) { if (y < x) x = y; }
template<typename T1, typename T2>inline void maxe(T1 &x, const T2 &y) { if (x < y) x = y; }

ostream& operator << (ostream &out, const vector<int> &b) {
    for (auto k : b) out << k << ' ';
    return out;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef char ch;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
typedef vector<ch> vch;
typedef vector<vch> vvch;
typedef vector<str> vs;



const int MOD = 1000000007;
const int INF = 1000000050;
const long long BIG = (long long)2e18 + 50;
const int MX = 600010;
const double EPS = 1e-9;
#ifdef LOCAL
    const int D = 4;
#else 
    const int D = 800;
#endif
const int PW = 19;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


int c[MX];
vi g[MX];
int eul[MX];
int tin[MX], tout[MX], timer = 0;
int up[MX][PW];

void dfs0(int v, int pr = 0) {
    up[v][0] = pr;
    for (int pw = 1; pw < PW; ++pw)
        up[v][pw] = up[up[v][pw - 1]][pw - 1]; 
    eul[timer] = v;
    tin[v] = timer++;
    fx(to, g[v]) {
        if (to != pr) {
            dfs0(to, v);
        }
    }
    eul[timer] = v;
    tout[v] = timer++;
}

bool anc(int a, int b) {
    return tin[a] <= tin[b] && tout[b] <= tout[a];
}
 
int lca(int a, int b) {
    if (anc(a, b)) return a;
    if (anc(b, a)) return b;
    for (int pw = PW - 1; pw >= 0; --pw) {
        if (!anc(up[a][pw], b)) {
            a = up[a][pw];
        }
    }
    return up[a][0];
} 
 
int bsum[D + 3];
int have[MX];


void inc(int v) {
    bsum[c[v] / D] -= have[c[v]];
    have[c[v]] ^= 1;
    bsum[c[v] / D] += have[c[v]];
}


int ask(int l, int r) {
    if (r - l < D) {
        for (int i = l; i <= r; ++i) {
            if (have[i]) {
                return i;
            }
        } 
    } else {
        while (l % D != 0) {
            if (have[l])
                return l;
            ++l;
        }
        while (r % D != D - 1) {
            if (have[r])
                return r;
            --r;
        }
        for (int i = l / D; i <= r / D; ++i) {
            if (bsum[i] > 0) {
                for (int j = i * D;; ++j) {
                    if (have[j]) {
                        return j;
                    }
                }
            }
        }
        
    }
    return -1;
}


int cl = 0;
int cr = -1;

void addl() {
    inc(eul[--cl]);
}

void addr() {
    inc(eul[++cr]);
}

void delr() {
    inc(eul[cr--]);
}

void dell() {
    inc(eul[cl++]);
}

int l[MX];
int r[MX];
int L[MX];
int R[MX];
int ans[MX];



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


    int n, q;
    cin >> n >> q;
    fi(0, n) {
        cin >> c[i];
    }

    fi(0, n - 1) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        g[a].pb(b);
        g[b].pb(a);
    }
    dfs0(0);
    vi reqs;
    fi(0, q) {
        reqs.pb(i);
        int a, b;
        cin >> a >> b >> l[i] >> r[i];
        --a, --b;
        if (tin[a] > tin[b])
            swap(a, b);
        if (anc(a, b)) {
            L[i] = tin[a];
            R[i] = tin[b];
        } else {
            L[i] = tout[a];
            R[i] = tin[b];
        }
    }
    sort(all(reqs), [&](int i, int j) {
        return (L[i] / D < L[j] / D) || (L[i] / D == L[j] / D && R[i] < R[j]);
    });
    fx(id, reqs) {
        while (cr < R[id])
            addr();
        while (cl > L[id])
            addl();
        while (cr > R[id])
            delr();
        while (cl < L[id])
            dell();
        int lc = lca(eul[L[id]], eul[R[id]]);
        if (lc != eul[L[id]])
            inc(lc);
        ans[id] = ask(l[id], r[id]);
        if (lc != eul[L[id]])
            inc(lc);
    }
    for (int i = 0; i < q; ++i)
        cout << ans[i] << '\n';
}