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>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 300050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
const int SIZ = 50000000 + 3;
char buf1[SIZ];
char *p1 = buf1, *p2 = buf1;
inline char readchar()
{
    if (p1 == p2)
        p1 = buf1, p2 = buf1 + fread(buf1, 1, SIZ, stdin);
    return p1 == p2 ? EOF : *p1++;
}
inline int read()
{
    int ret, c;
    while ((c = readchar()) > '9' || c < '0')
        ;
    ret = c - '0';
    while ((c = readchar()) >= '0' && c <= '9')
        ret = ret * 10 + c - '0';
    return ret;
}

int n, Q, a[N];
int euler[N << 1], tim, in[N], out[N];
int belong[N << 1], B, bl[1050], br[1050];
struct querys
{
    int id;
    int u, v, l, r, lca;
    int L, R;
    querys() {}
    querys(int id, int u, int v, int l, int r) : id(id), u(u), v(v), l(l), r(r) {}
    bool operator<(const querys &rhs) const
    {
        return belong[L] != belong[rhs.L] ? L < rhs.L : ((belong[L] & 1) ? R < rhs.R : R > rhs.R);
    }
} q[N];
const int MAXN = 300050, MAXM = 600050;
struct Edge
{
    int v, nxt;
} e[MAXM];
int head[MAXN], ecnt;
void add_edge(int u, int v)
{
    e[++ecnt] = {v, head[u]}, head[u] = ecnt;
    e[++ecnt] = {u, head[v]}, head[v] = ecnt;
}
int dep[MAXN], fa[MAXN][20], dfn[MAXN], dfncnt, m;
void LCA_pre_dfs(int u, int f, int d)
{
    dep[u] = d;
    fa[u][0] = f;
    dfn[u] = ++dfncnt;
    euler[++tim] = u;
    in[u] = tim;
    for (int i = head[u]; i; i = e[i].nxt)
    {
        if (e[i].v != f)
            LCA_pre_dfs(e[i].v, u, d + 1);
    }
    euler[++tim] = u;
    out[u] = tim;
}
int ans[N];
void LCA_pre()
{
    LCA_pre_dfs(1, 0, 1);
    for (int j = 1; j <= 19; j++)
        for (int i = 1; i <= n; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
inline int getlca(int u, int v)
{
    if (dep[u] < dep[v])
        swap(u, v);
    int delta = dep[u] - dep[v];
    for (int i = 19; i >= 0; i--)
        if ((delta >> i) & 1)
            u = fa[u][i];
    for (int i = 19; i >= 0; i--)
        if (fa[u][i] ^ fa[v][i])
        {
            u = fa[u][i];
            v = fa[v][i];
        }
    if (u == v)
        return u;
    return fa[u][0];
}
int tt[1050];
inline void update(int &c, int val)
{
    tt[belong[c]] += val;
}
int used[N], cnt[N];
inline void add(int &c)
{
    if (cnt[a[c]] & 1)
        update(a[c], -1);
    cnt[a[c]]++;
    if (cnt[a[c]] & 1)
        update(a[c], 1);
}
inline void del(int &c)
{
    if (cnt[a[c]] & 1)
        update(a[c], -1);
    cnt[a[c]]--;
    if (cnt[a[c]] & 1)
        update(a[c], 1);
}
inline void Add(int &c)
{
    used[c] ? del(c) : add(c);
    used[c] ^= 1;
}
inline void getans(const querys &nowq)
{
    int lca = nowq.lca, l = nowq.l, r = nowq.r;
    if (lca)
    {
        int c = lca;
        if (cnt[a[c]] & 1)
            update(a[c], -1);
        cnt[a[c]]++;
        if (cnt[a[c]] & 1)
            update(a[c], 1);
    }
    int res = -1;
    if (belong[l] == belong[r] || belong[l] == belong[r] - 1)
    {
        for (int i = l; i <= r; ++i)
            if (cnt[i] & 1)
            {
                res = i;
                break;
            }
    }
    else
    {
        for (int i = l; belong[i] <= belong[l]; ++i)
        {
            if (cnt[i] & 1)
            {
                res = i;
                break;
            }
        }
        if (res == -1)
        {
            for (int i = r; belong[i] >= belong[r]; --i)
            {
                if (cnt[i] & 1)
                {
                    res = i;
                    break;
                }
            }
        }
        if (res == -1)
        {
            for (int i = belong[l] + 1; i < belong[r]; ++i)
            {
                if (tt[i])
                {
                    for (int j = bl[i]; j <= br[i]; ++j)
                        if (cnt[j] & 1)
                        {
                            res = j;
                            break;
                        }
                    break;
                }
            }
        }
    }
    ans[nowq.id] = res;
    if (lca)
    {
        int c = lca;
        if (cnt[a[c]] & 1)
            update(a[c], -1);
        cnt[a[c]]--;
        if (cnt[a[c]] & 1)
            update(a[c], 1);
    }
}

inline void solve()
{
    memarray(ans, -1), memarray(bl, inf);
    n = read(), Q = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i < n; ++i)
    {
        int x = read(), y = read();
        add_edge(x, y);
    }
    LCA_pre();
    for (int i = 1; i <= Q; ++i)
    {
        int u, v, l, r;
        u = read(), v = read(), l = read(), r = read();
        q[i] = (querys){i, u, v, l, r};
        int _lca = getlca(u, v);
        if (in[u] > in[v])
            swap(u, v);
        if (_lca == u || _lca == v)
            q[i].L = in[u], q[i].R = in[v];
        else
            q[i].L = out[u], q[i].R = in[v], q[i].lca = _lca;
    }
    B = 550;
    for (int i = 1; i <= n * 2; ++i)
    {
        belong[i] = i / B + 1;
        if (i <= n)
            bl[belong[i]] = min(bl[belong[i]], i), br[belong[i]] = max(br[belong[i]], i);
    }
    sort(q + 1, q + Q + 1);
    int L = 1, R = 0;
    for (int i = 1; i <= Q; ++i)
    {
        while (L > q[i].L)
            --L, Add(euler[L]);
        while (R > q[i].R)
            Add(euler[R]), --R;
        while (R < q[i].R)
            ++R, Add(euler[R]);
        while (L < q[i].L)
            Add(euler[L]), ++L;
        getans(q[i]);
    }
    for (int i = 1; i <= Q; ++i)
        printf("%d\n", ans[i]);
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}