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 <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert> 
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>
#include <stack>
#include <limits>

using namespace std;

// #define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

istream& operator>> (istream& in, pii& b) {
    in >> b.first >> b.second;
    return in;
}

ostream& operator<< (ostream& out, const pii& b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}

template<typename T> ostream& operator<< (ostream& out, const vector<T>& a) {
    for (auto k : a) out << k << " ";
    return out;
}

template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << endl;
    // const long long INF = 1e18;
    // const long long mod = 2600000069;
    // const long long p = 10;
#else
    #define dbg(x) 57
    // const long long INF = 1e18;
    // const long long mod = 2600000069;  
    // const long long p = 179;
#endif

const ld PI = 4 * atan(1);

#define time clock() / (double) CLOCKS_PER_SEC

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,sse3,sse4")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("avx2")

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 3e5 + 10;
const int BUBEN = 600;
const int K = 19;

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

int tin[N], tout[N];
int tour[N + N];

int d[N];
int up[N][K];

int curt = -1;

void dfs(int v, int p = -1) {
    up[v][0] = p;
    for (int i = 1; i < K; i++) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    tin[v] = ++curt;
    tour[tin[v]] = v;
    for (auto u : g[v]) {
        if (u != p) {
            d[u] = d[v] + 1;
            dfs(u, v);
        }
    }
    tout[v] = ++curt;
    tour[tout[v]] = v;
}

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

int up_d(int v, int d) {
    for (int i = K - 1; i >= 0; i--) {
        if ((d >> i) & 1) {
            v = up[v][i];
        }
    }
    return v;
}

int lca(int u, int v) {
    if (ancestor(u, v)) return u;
    if (ancestor(v, u)) return v;
    if (d[u] < d[v]) v = up_d(v, d[v] - d[u]);
    if (d[v] < d[u]) u = up_d(u, d[u] - d[v]);
    if (u == v) return u;
    for (int i = K - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i], v = up[v][i];
        }
    }
    return up[v][0];
}

struct inf {
    int l, r, lo, hi, ind;
    inf() {}
    inf(int l_, int r_, int lo_, int hi_, int ind_) {
        l = l_, r = r_, lo = lo_, hi = hi_, ind = ind_;
    }
};

bool comp(const inf& a, const inf& b) {
    return a.r < b.r;
}

vector<inf> b[N];

int cnt[N];
int bcnt[N];

void add(int x) {
    int block = x / BUBEN;
    bcnt[block] -= cnt[x];
    cnt[x] ^= 1;
    bcnt[block] += cnt[x];
}

int find_ans(int l, int r) {
    int bl = l / BUBEN;
    int br = r / BUBEN;
    if (bl == br) {
        for (int i = l; i <= r; i++) {
            if (cnt[i]) return i;
        }
        return -1;
    }
    for (int i = l; i <= (bl + 1) * BUBEN - 1; i++) {
        if (cnt[i]) {
            return i;
        }
    }
    for (int i = br * BUBEN; i <= r; i++) {
        if (cnt[i]) {
            return i;
        }
    }
    for (int i = bl + 1; i < br; i++) {
        if (bcnt[i]) {
            for (int j = i * BUBEN; j <= (i + 1) * BUBEN; j++) {
                if (cnt[j]) {
                    return j;
                }
            }
        }
    }
    return -1;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int v, u;
        cin >> v >> u;
        v--, u--;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(0, 0);
    // for (int i = 0; i <= curt; i++) {
    //     cout << tour[i] << " ";
    // }
    // cout << "\n";
    for (int i = 0; i < q; i++) {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        u--, v--;
        if (tin[u] <= tin[v] && tout[v] <= tout[u]) {
            // cout << tin[u] << " " << tin[v] << "\n";
            b[tin[u] / BUBEN].pb(inf(tin[u], tin[v], l, r, i));
        } else if (tin[v] <= tin[u] && tout[u] <= tout[v]) {
            // cout << tin[v] << " " << tin[u] << "\n";
            b[tin[v] / BUBEN].pb(inf(tin[v], tin[u], l, r, i));
        } else {
            if (tout[v] >= tin[u]) swap(u, v);
            // cout << tout[v] << " " << tin[u] << "\n";
            b[tout[v] / BUBEN].pb(inf(tout[v], tin[u], l, r, i));
        }
    }
    for (int i = 0; i <= (n + n - 1) / BUBEN; i++) {
        curt = i + 1;
        sort(all(b[i]), comp);
        int l = i * BUBEN;
        int r = l;
        for (auto w : b[i]) {
            while (r <= w.r) {
                add(a[tour[r]]);
                r++;
            }
            while (r - 1 > w.r) {
                add(a[tour[r - 1]]);
                r--;
            }
            while (l < w.l) {
                add(a[tour[l]]);
                l++;
            }
            while (l > w.l) {
                l--;
                add(a[tour[l]]);
            }
            int u = tour[w.l], v = tour[w.r];
            int p = lca(u, v);
            if (p != u && p != v) {
                add(a[p]);
            }
            ans[w.ind] = find_ans(w.lo, w.hi);
            if (p != u && p != v) {
                add(a[p]);
            }
        }
        for (int j = l; j < r; j++) {
            add(a[tour[j]]);
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
}
/*
6 1
3 2 1 3 1 3
1 2
1 3
2 4
2 5
4 6
1 4 1 5
*/