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(2)
#pragma GCC optimize(3)

#include <bits/stdc++.h>

using namespace std;

template<typename T>
inline T read() {
    T s = 0, f = 1; int ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
    return s * f;
}
#define gl() read<ll>()
#define gn() read<int>()

#define ll long long
#define INF 0x3f3f3f3f

constexpr int N = 3e5 + 100;

int n, m;

int a[N];

mt19937 rnd(233);

ll rd[N];

struct SegmentTree {
    static const int N = 3e5 + 100;
#define lson(x) s[x].lc
#define rson(x) s[x].rc

    struct node {
        int lc, rc;
        ll sum;
    } s[N * 80];

    int tot = 0;

    void insert(int &now, int l, int r, int id, int val) {
        if (not now) now = ++tot;
        s[now].sum ^= rd[id];
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (id <= mid) insert(lson(now), l, mid, id, val);
        else insert(rson(now), mid + 1, r, id, val);
    }

    int getid(int st, int ed, int fa, int gfa, int l, int r) {
        if (l == r) {
            if (s[st].sum ^ s[ed].sum ^ s[fa].sum ^ s[gfa].sum) return l;
            return -1;
        }
        int mid = (l + r) >> 1;
        ll num = s[lson(st)].sum ^ s[lson(ed)].sum ^ s[lson(fa)].sum ^ s[lson(gfa)].sum;
//        cout << "****" << num << endl;
        if (num != 0) return getid(lson(st), lson(ed), lson(fa), lson(gfa), l, mid);

        num = s[rson(st)].sum ^ s[rson(ed)].sum ^ s[rson(fa)].sum ^ s[rson(gfa)].sum;
        if (num != 0) return getid(rson(st), rson(ed), rson(fa), rson(gfa), mid + 1, r);

        return -1;
    }

    int query(int st, int ed, int fa, int gfa, int l, int r, int L, int R) {
        if (l == L and R == r) {
//            cout << l << " " << r << " " << getid(st, ed, fa, gfa, l, r) << endl;
            return getid(st, ed, fa, gfa, l, r);
        }
        int mid = (l + r) >> 1;
        if (R <= mid) return query(lson(st), lson(ed), lson(fa), lson(gfa), l, mid, L, R);
        else if (L > mid) return query(rson(st), rson(ed), rson(fa), rson(gfa), mid + 1, r, L, R);
        else {
            int num = query(lson(st), lson(ed), lson(fa), lson(gfa), l, mid, L, mid);
            if (num != -1) return num;
            else return query(rson(st), rson(ed), rson(fa), rson(gfa), mid + 1, r, mid + 1, R);
        }
    }

    void merge(int &u, int v) {
        if (not u or not v) {
            u += v;
            return ;
        }

        s[u].sum ^= s[v].sum;

        merge(lson(u), lson(v));
        merge(rson(u), rson(v));
    }

} tree;

int root[N];
vector<int> v[N];

int dep[N], dp[N][25];

void dfs(int node, int fa) {
    dep[node] = dep[fa] + 1;
    dp[node][0] = fa;
    for (int i = 1; (1 << i) <= dep[node]; ++i) {
        dp[node][i] = dp[dp[node][i - 1]][i - 1];
    }
    for (auto to : v[node]) {
        if (to == fa) continue;
        tree.merge(root[to], root[node]);
        dfs(to, node);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int tem = dep[x] - dep[y];
    for (int i = 0; tem; ++i) {
        if (tem & 1) x = dp[x][i];
        tem >>= 1;
    }
    if (x == y) return x;
    for (int j = 21; j >= 0 and x != y; --j) {
        if (dp[x][j] != dp[y][j]) {
            x = dp[x][j];
            y = dp[y][j];
        }
    }
    return dp[x][0];
}

int main() {
    n = gn(), m = gn();
    for (int i = 1; i <= n; ++i) {
        rd[i] = rnd();
//        cout << rd[i] << endl;
    }
    for (int i = 1; i <= n; ++i) {
        a[i] = gn();
        tree.insert(root[i], 1, n, a[i], 1);
    }

    for (int i = 1; i < n; ++i) {
        int x = gn(), y = gn();
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1, 0);

    for (int i = 1; i <= m; ++i) {
        int u = gn(), t = gn(), l = gn(), r = gn();
        int fa = lca(u, t);
//        cout << "query" << " " << u << " " << t << endl;
//        cout << fa << endl;
        int num = tree.query(root[u], root[t], root[fa], root[dp[fa][0]], 1, n, l, r);
        cout << num << endl;
    }

}