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 ll              long long 
#define pb              push_back
#define all(v)          v.begin(),v.end()
#define sz(a)           (ll)a.size()
#define F               first
#define S               second
#define INF             2000000000000000000
#define popcount(x)     __builtin_popcountll(x)
#define pll             pair<ll,ll> 
#define pii             pair<int,int>
#define ld              long double

const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);

template<typename T, typename U> static inline void amin(T &x, U y){ if(y<x) x=y; }
template<typename T, typename U> static inline void amax(T &x, U y){ if(x<y) x=y; }
template<typename T, typename U> ostream& operator<<(ostream &os, const pair<T, U> &p)
{ 
    return os<<'('<<p.F<< ","<<p.S<<')'; 
}

//RNG based on mersenne_twister 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());


const int NN = 15000000;
struct node{
    ll val;
    int L,R;
    node (): L(-1),R(-1),val(0){};
    node(ll x) : L(-1),R(-1),val(x){};
};
struct PERTREE{
    node tree[NN];
    int cursz=0;
    int buildTree(ll st,ll en)
    {
        ll v = cursz++;
        tree[v]=node();
        if(st==en)
            return v;
        ll mid=(st+en)>>1;
        tree[v].L=buildTree(st,mid);
        tree[v].R=buildTree(mid+1,en); 
        return v;
    }
    int update(ll v,ll st,ll en,ll pos,ll val)
    {
        ll u=cursz++;
        tree[u] = tree[v];
        if(st==en)
        {
            tree[u].val ^= val;
            return u;
        }
        ll mid=(st+en)>>1;
        if(pos<=mid)
            tree[u].L=update(tree[v].L,st,mid,pos,val);
        else 
            tree[u].R=update(tree[v].R,mid+1,en,pos,val);
        tree[u].val = tree[tree[u].L].val ^ tree[tree[u].R].val;
        return u;
    }
    int query(int r1,int r2,int st,int en,int l,int r)
    {
        if(st>r || en<l)
            return -1;
        if((tree[r1].val ^ tree[r2].val) == 0)
            return -1;
        if(st == en)
            return st;
        int mid=(st+en)>>1;
        int u = query(tree[r1].L,tree[r2].L,st,mid,l,r);
        if(u != -1)
            return u;
        return query(tree[r1].R,tree[r2].R,mid+1,en,l,r);
    }
}seg;

const int N = 600005;

int a[N];
vector<int> v[N];
 
int par[N][20],dep[N];
int pos[N];
int roots[N];
int n;
ll h[N];

void dfs(int s,int p)
{
    roots[s] = seg.update(roots[p],1,n,a[s],h[a[s]]);
    par[s][0] = p;
    for(int i=1;i<20;++i)
        par[s][i] = par[par[s][i-1]][i-1];
    for(auto &j:v[s])
    {
        if(j!=p)
        {
            dep[j] = dep[s] + 1;
            dfs(j,s);
        }
    }
}

int _runtimeTerror_()
{
    int Q;
    cin>>n>>Q;
    for(int i=1;i<=n;++i)
        cin >> a[i];
    for(int i=0;i<n-1;++i)
    {
        int x,y;
        cin >> x >> y;
        v[x].pb(y),v[y].pb(x);
    }
    for(int i=1;i<=n;++i)
        h[i] = rng()%(1LL<<62);
    roots[0] = seg.buildTree(1,n);
    dfs(1,0);
    auto lca = [&](int u,int v)
    {
        if(dep[u]>dep[v])
            swap(u,v);
        int d = dep[v] - dep[u];
        for(int i=0;i<20;++i)
            if(d&(1<<i))
                v = par[v][i];
        if(u == v)
            return u;
        for(int i=19;i>=0;--i)
        {
            if(par[u][i] != par[v][i])
                u = par[u][i],v = par[v][i];
        }
        return par[u][0];
    };
    for(int i=1;i<=Q;++i)
    {
        int u,v,l,r;
        cin>>u>>v>>l>>r;
        int lc = lca(u,v);
        int t = seg.update(roots[u],1,n,a[lc],h[a[lc]]);
        cout << seg.query(roots[v],t,1,n,l,r) << "\n";
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef runSieve
        sieve();
    #endif
    #ifdef NCR
        initialize();
    #endif
    int TESTS=1;
    //cin>>TESTS;
    while(TESTS--)
        _runtimeTerror_();
    return 0;
}