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;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnf(2106);
const int N = 600005, L = 21;

int ka()
{
    int x = 0;
    while (1)
    {
        char y = getchar();
        if ('0' <= y && y <= '9')
            x = x * 10 + y - '0';
        else
            return x;
    }
}

int n, qq;
int a[N];
vector<int> g[N];
ll u[N];

vector<int> v;
int p[N][L];
void dfs(int x, int p0)
{
    p[x][0] = p0;
    for (int i = 1; i < L; ++i)
        p[x][i] = p[p[x][i - 1]][i - 1];

    v.push_back(x);
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p0)
            continue;
        dfs(h, x);
    }
    v.push_back(x);
}

int f[N], s[N];

bool isp(int x, int y)
{
    return (f[x] <= f[y] && f[y] <= s[x]);
}

int lca(int x, int y)
{
    if (isp(x, y))
        return x;
    if (isp(y, x))
        return y;
    for (int i = L - 1; i >= 0; --i)
    {
        if (!isp(p[x][i], y))
            x = p[x][i];
    }
    return p[x][0];
}

ll t[N * L];
int z;
int ul[N * L], ur[N * L];

int ubd(int tl, int tr, int x, ll y, int pos)
{
    int ypos = ++z;
    ul[ypos] = ul[pos];
    ur[ypos] = ur[pos];
    if (tl == tr)
    {
        t[ypos] = (t[pos] ^ y);
        return ypos;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ul[ypos] = ubd(tl, m, x, y, ul[pos]);
    else
        ur[ypos] = ubd(m + 1, tr, x, y, ur[pos]);
    t[ypos] = (t[ul[ypos]] ^ t[ur[ypos]]);
    return ypos;
}

ll qry(int tl, int tr, int l, int r, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return t[pos];
    int m = (tl + tr) / 2;
    return (qry(tl, m, l, min(m, r), ul[pos]) ^
            qry(m + 1, tr, max(m + 1, l), r, ur[pos]));
}

int qryf(int tl, int tr, int l, int r, int z, ll h, int posx, int posy)
{
    if (tl == l && tr == r)
    {
        ll hh = (t[posx] ^ t[posy]);
        if (a[z] <= r)
            hh ^= u[a[z]];
        if (hh == h)
            return -1;
        if (tl == tr)
            return tl;

        int m = (tl + tr) / 2;
        int u = qryf(tl, m, l, m, z, h, ul[posx], ul[posy]);
        if (u != -1)
            return u;
        return qryf(m + 1, tr, m + 1, r, z, (h ^ t[ul[posx]] ^ t[ul[posy]]), ur[posx], ur[posy]);
    }
    int m = (tl + tr) / 2;
    if (r <= m)
        return qryf(tl, m, l, r, z, h, ul[posx], ul[posy]);
    if (l > m)
        return qryf(m + 1, tr, l, r, z, (h ^ t[ul[posx]] ^ t[ul[posy]]), ur[posx], ur[posy]);
    int u = qryf(tl, m, l, m, z, h, ul[posx], ul[posy]);
    if (u != -1)
        return u;
    return qryf(m + 1, tr, m + 1, r, z, (h ^ t[ul[posx]] ^ t[ul[posy]]), ur[posx], ur[posy]);
}

int root[N];

ll qryy(int x, int y, int z, int t)
{
    if (a[z] <= t)
        return (qry(1, n, 1, t, root[f[x]]) ^ u[a[z]] ^ qry(1, n, 1, t, root[f[y]]));
    return (qry(1, n, 1, t, root[f[x]]) ^ qry(1, n, 1, t, root[f[y]]));
}

void solv()
{
    n = ka();
    qq = ka();
    for (int i = 1; i <= n; ++i)
        a[i] = ka();
    for (int i = 0; i < n - 1; ++i)
    {
        int x, y;
        x = ka();
        y = ka();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i = 1; i <= n; ++i)
        u[i] = rnd();

    v.push_back(-1);
    dfs(1, 1);

    for (int i = 1; i <= n * 2; ++i)
    {
        if (f[v[i]] == 0)
            f[v[i]] = i;
        else
            s[v[i]] = i;
    }
    for (int i = 1; i <= n * 2; ++i)
        root[i] = ubd(1, n, a[v[i]], u[a[v[i]]], root[i - 1]);

    while (qq--)
    {
        int x, y, l, r;
        x = ka();
        y = ka();
        l = ka();
        r = ka();
        int z = lca(x, y);

        ll h = qryy(x, y, z, l - 1);
        printf("%d\n", qryf(1, n, l, r, z, h, root[f[x]], root[f[y]]));
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    int tt = 1;
    //scanf("%d", &tt);
    while (tt--)
        solv();
    return 0;
}