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;

const int N = 3e5+5;
const int M = 3e5+5;
vector <vector <int> >adj;
int start[N],finish[N];
int arr[N];
int visit[2*N];
int somoy = 0;
int height[N],first[N],visited[N];


struct LCA
{
    vector<int> euler, segtree;

    int n;

    LCA(vector<vector<int> > &adj, int root = 0)
    {
        n = adj.size();
        euler.reserve(n * 2);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }

    void dfs(vector<vector<int> > &adj, int node, int h = 0)
    {
        start[node] = somoy;
        visit[somoy]= node;
        somoy++;
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node])
        {
            if (!visited[to])
            {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
        finish[node]=somoy;
        visit[somoy]= node;
        somoy++;
    }

    void build(int node, int b, int e)
    {
        if (b == e)
        {
            segtree[node] = euler[b];
        }
        else
        {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }

    int query(int node, int b, int e, int L, int R)
    {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;

        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1)
            return right;
        if (right == -1)
            return left;
        return height[left] < height[right] ? left : right;
    }

    int lca(int u, int v)
    {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};

int a[N];
int b[N];
int len;
int block;
struct query
{
    int l,r,idx;
    int ancestor;
    int x1,x2;
};
bool comp1(query &p,query &q)
{
    if (p.l / block != q.l / block)
    {
        if(p.l==q.l)
            return p.r<q.r;
        return p.l < q.l;
    }
    return (p.l / block & 1) ? (p.r < q.r) : (p.r > q.r);
}

vector<query>qarra;
int vertexcnt[M];
bool cnt[N];
int ans[N];

inline void Add(int i)
{
    cnt[i]^=1;
    if(cnt[i]==0)
    {
        a[i]--;
        b[i/len]--;
    }
    else
    {
        a[i]++;
        b[i/len]++;
    }

}
inline void Remove(int i)
{
    cnt[i]^=1;
    if(cnt[i]==0)
    {
        a[i]--;
        b[i/len]--;
    }
    else
    {
        a[i]++;
        b[i/len]++;
    }
}
int get_ans(int x, int y)
{
    int b1 = x/len;
    int b2 = y/len;
    for(int i=b1+1; i<=b2-1; i++)
    {
        if(b[i])
        {
            for(int j=i*len;; j++)
            {
                if(a[j])
                    return j;
            }
        }
    }
    for(int j=b1*len; j<(b1+1)*len; j++)
    {
        if(j>=x && j<=y && a[j])
            return j;
    }
    for(int j=b2*len; j<(b2+1)*len; j++)
    {
        if(j>=x && j<=y && a[j])
            return j;
    }
    return -1;

}




int32_t main()
{
#ifndef APURBA
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif

    int n,q;
    cin>>n>>q;
    adj.resize(n);
    len = (int) sqrt (n + .0) + 1;
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    for(int i=0; i<n-1; i++)
    {
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    LCA lca(adj,0);
    qarra.reserve(q);
    for(int i=0; i<q; i++)
    {
        int u,v, x,y;
        cin>>u>>v>>x>>y;
        u--;
        v--;
        if(start[u]>start[v])
            swap(u,v);
        int l = lca.lca(u,v);
        if(l==u)
        {
            qarra.push_back({start[u],start[v],i, l,x,y});
        }
        else
        {
            qarra.push_back({finish[u],start[v],i, l,x,y});
        }
    }
    block = (int)sqrt(2*n);
    sort(qarra.begin(),qarra.end(),comp1);
    int currL=0,currR=-1;
    for(int i=0; i<q; i++)
    {
        int l= qarra[i].l,r=qarra[i].r;
        int ara = qarra[i].x1, bara = qarra[i].x2;
        while(currL < l)
        {
            vertexcnt[visit[currL]]--;
            if(vertexcnt[visit[currL]]==0)
            {
                Remove(arr[visit[currL]]);
            }
            else if(vertexcnt[visit[currL]]==1)
            {
                Add(arr[visit[currL]]);
            }
            currL++;
        }
        while(currL> l)
        {
            currL--;
            vertexcnt[visit[currL]]++;
            if(vertexcnt[visit[currL]]==1)
            {
                Add(arr[visit[currL]]);
            }
            else if(vertexcnt[visit[currL]]==2)
            {
                Remove(arr[visit[currL]]);
            }
        }
        while(currR < r)
        {
            currR++;
            vertexcnt[visit[currR]]++;
            if(vertexcnt[visit[currR]]==1)
            {
                Add(arr[visit[currR]]);
            }
            else if(vertexcnt[visit[currR]]==2)
            {
                Remove(arr[visit[currR]]);
            }
        }
        while(currR > r)
        {
            vertexcnt[visit[currR]]--;
            if(vertexcnt[visit[currR]]==0)
            {
                Remove(arr[visit[currR]]);
            }
            else if(vertexcnt[visit[currR]]==1)
            {
                Add(arr[visit[currR]]);
            }
            currR--;
        }
        int sawa = qarra[i].ancestor;
        if( sawa != visit[currL])
        {
            Add(arr[sawa]);
            ans[qarra[i].idx]=get_ans(ara,bara);
            Remove(arr[sawa]);
        }
        else
        {
            ans[qarra[i].idx]=get_ans(ara,bara);
        }
    }
    for(int i=0; i<q; i++)
    {
        cout<<ans[i]<<"\n";
    }
    return 0;
}