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:
// To Hell and Back
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 3e5 + 10, MOD = 1e9 + 7;
int pw[N], A[N], H[N], P[20][N], n, q; vector<int> adj[N];

struct node {
    int h;
    node *lc, *rc;
    
    node() : h(), lc(this), rc(this) {}

    node* upd(int p, int l = 1, int r = n + 1) {
        node* nw = new node(*this);
        if (r - l < 2) {
            nw->h ^= 1;
            return nw;
        }
        int md = (l + r) >> 1;
        if (p < md) 
            nw->lc = lc->upd(p, l, md);
        else 
            nw->rc = rc->upd(p, md, r);
        nw->h = (pw[r- md] * 1ll * nw->lc->h % MOD + nw->rc->h) % MOD;
        return nw;
    }

    friend int get(int p, node* u, node* v, int l = 1, int r = n + 1) {
        if (u->h == v->h || r <= p) return -1;
        if (r - l < 2) 
            return l;
        int md = (l + r) >> 1;
        int x = get(p, u->lc, v->lc, l, md);
        if (~x) return x;
        return get(p, u->rc, v->rc, md, r);
    }

};

node* root[N];
void preDFS(int v, int p = 0) {
    if (!p) P[0][v] = v;
    root[v] = root[p]->upd(A[v]);
    for (int i = 1; i < 20; i++) 
        P[i][v] = P[i - 1][P[i - 1][v]];
    for (int u : adj[v]) {
        if (u != p) 
            H[u] = H[v] + 1, P[0][u] = v, preDFS(u, v);
    }
}

int LCA(int u, int v) {
    if (H[u] < H[v]) swap(u, v);
    for (int i = H[u] - H[v]; i; i -= i & -i) 
        u = P[__builtin_ctz(i)][u];
    for (int i = 19; i--; ) 
        if (P[i][u] != P[i][v]) 
            u = P[i][u], v = P[i][v];
    return u == v ? v : P[0][v];
}

int main() {
    pw[0] = 1;
    for (int i = 1; i < N; i++) 
        pw[i] = pw[i - 1] * 2ll % MOD;
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) 
        scanf("%d", &A[i]);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    root[0] = new node(); 
    preDFS(1);
    for (; q; q--) {
        int u, v, l, r; scanf("%d%d%d%d", &u, &v, &l, &r);
        int ret = get(l, root[u], root[v]), p = LCA(u, v);
        if (ret == A[p]) 
            ret = get(ret + 1, root[u], root[v]);
        else if ((ret > r || !~ret) && (l <= A[p] && A[p] <= r)) ret = A[p];
        printf("%d\n", ret > r ? -1 : ret);
    }
    return 0;
}