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;
typedef long long ll;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll l,ll r) {return uniform_int_distribution<ll>(l,r)(gen);}

const int N=300005;
ll x[N];

struct Node
{
    ll h;
    Node *l,*r;
    Node(ll a):h(a){l=r=nullptr;}
    Node(Node *a,Node *b):l(a),r(b){h=(l->h^r->h);}
};

Node* build(int l,int r)
{
    if(l==r) return new Node(0);
    int m=(l+r)/2;
    return new Node(build(l,m),build(m+1,r));
}

Node* update(Node *now,int l,int r,int pos)
{
    if(l==r) return new Node(now->h^x[l]);
    int m=(l+r)/2;
    if(pos<=m) return new Node(update(now->l,l,m,pos),now->r);
    else return new Node(now->l,update(now->r,m+1,r,pos));
}

int query(Node *a,Node *b,int l,int r,int ql,int qr)
{
    if(ql>qr) return -1;
    if(l==ql&&r==qr&&a->h==b->h) return -1;
    if(l==r) return l;
    int m=(l+r)/2;
    int res=query(a->l,b->l,l,m,ql,min(qr,m));
    if(res!=-1) return res;
    return query(a->r,b->r,m+1,r,max(ql,m+1),qr);
}

int n;
vector<int> v[N];
int val[N];
vector<Node*> st(N);
int depth[N];
int p[N][19];

void dfs(int a)
{
    depth[a]=depth[p[a][0]]+1;
    for(int i=1;i<19;i++) p[a][i]=p[p[a][i-1]][i-1];
    st[a]=update(st[p[a][0]],1,n,val[a]);
    for(int to:v[a])
    {
        if(to==p[a][0]) continue;
        p[to][0]=a;
        dfs(to);
    }
}

int lca(int a,int b)
{
    if(depth[a]>depth[b]) swap(a,b);
    for(int i=18;i>=0;i--) if(depth[p[b][i]]>=depth[a]) b=p[b][i];
    if(a==b) return a;
    for(int i=18;i>=0;i--) if(p[a][i]!=p[b][i]) tie(a,b)={p[a][i],p[b][i]};
    return p[a][0];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int q;
    cin >> n >> q;
    for(int i=1;i<=n;i++) x[i]=rng(1,(1ll<<62));
    for(int i=1;i<=n;i++) cin >> val[i];
    for(int i=1;i<=n-1;i++)
    {
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    st[0]=build(1,n);
    dfs(1);
    while(q--)
    {
        int a,b,l,r;
        cin >> a >> b >> l >> r;
        Node *two=update(st[b],1,n,val[lca(a,b)]);
        cout << query(st[a],two,1,n,l,r) << "\n";
    }
    return 0;
}