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 <cassert>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

const int N_MAX = 3e5, B = 500;
bool seen[N_MAX];
int N, Q, a[N_MAX], sol[N_MAX];
vector<int> G[N_MAX];
struct query {int id, u, v, l, r, extra;};
query q[N_MAX];
int e[2*N_MAX], h[2*N_MAX], E, l1[N_MAX];
int c[2*N_MAX], C, l2[N_MAX], r2[N_MAX];

void DFS(int u, int height) {
    seen[u] = true;
    l1[u] = E; e[E] = u; h[E] = height; E++;
    l2[u] = C; c[C] = a[u]; C++;
    for (int v: G[u]) {
        if(seen[v]) continue;
        DFS(v, height+1);
        e[E] = u; h[E] = height; E++;
    }
    r2[u] = C; c[C] = a[u]; C++;
}

int lca[4*N_MAX];
void init1() {
    for (int i = 0; i < E; i++) lca[i+E] = i;
    for (int i = E-1; i > 0; --i)
        lca[i] = (h[lca[i<<1]] < h[lca[i<<1|1]] ? lca[i<<1] : lca[i<<1|1]);
}

int query1(int l, int r) {
    int opt = N, ans = -1;
    for (l += E, r += E; l < r; l >>= 1, r >>= 1) {
        if (l&1) {
            if(opt > h[lca[l]]) opt = h[lca[l]], ans = lca[l];
            ++l;
        }
        if (r&1) {
            --r;
            if(opt > h[lca[r]]) opt = h[lca[r]], ans = lca[r];
        }
    }
    return ans;
}

int LCA(int u, int v) {
    return e[query1(min(l1[u], l1[v]), max(l1[u], l1[v])+1)];
}

bool odd[N_MAX];
int lazy[N_MAX/B+1];

void add(int x) {
    lazy[x/B] += (odd[x] ? -1 : 1);
    odd[x] ^= 1;
}

int query2(int l, int r) {
    while(l <= r && l%B) if(odd[l++]) return l-1;
    while(l <= r && r%B != B-1) if(odd[r--]) return r+1;
    if(l > r) return -2;
    l /= B, r /= B;
    while(l <= r) {
        if(lazy[l]) {
            int i = l*B;
            while(!odd[i]) i++;
            return i;
        }
        l++;
    }
    return -2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> Q;
    for (int i = 0; i < N; i++) {cin >> a[i]; a[i]--;}
    for (int i = 0; i < N-1; i++) {
        int x, y; cin >> x >> y; x--; y--;
        G[x].push_back(y); G[y].push_back(x);
    }
    DFS(0, 0);
    init1();
    for (int i = 0; i < Q; i++) {
        q[i].id = i;
        int u, v; cin >> u >> v; u--; v--;
        if(l2[u] > l2[v]) swap(u, v);
        if(r2[u] <= l2[v]) {
            q[i].u = r2[u];
            q[i].v = l2[v];
            q[i].extra = a[LCA(u,v)];
        }
        else {
            q[i].u = l2[u];
            q[i].v = l2[v];
            q[i].extra = -1;
        }
        cin >> q[i].l >> q[i].r;
        q[i].l--; q[i].r--;
    }
    sort(q, q+Q, [](const query & a, const query & b) -> bool {
        if(a.u/B == b.u/B) return ((a.u/B)%2 == 0 ? a.v < b.v : a.v > b.v);
        return (a.u/B < b.u/B);
    });

    int U = 0, V = -1;
    for (int i = 0; i < Q; i++) {
        while(V < q[i].v) add(c[++V]);
        while(V > q[i].v) add(c[V--]);
        while(U < q[i].u) add(c[U++]);
        while(U > q[i].u) add(c[--U]);
        if(q[i].extra != -1) add(q[i].extra);
        sol[q[i].id] = query2(q[i].l, q[i].r);
        if(q[i].extra != -1) add(q[i].extra);
    }
    for (int i = 0; i < Q; i++)
        cout << sol[i]+1 << "\n";

    return 0;
}