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>
#define ll long long
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
namespace fast_io {
    const int BUFSIZE = 50 << 20;
    char Buf[BUFSIZE + 1], *buf = Buf;
    char OBuf[BUFSIZE + 1] , *obuf = OBuf;

    void init() {
        Buf[fread(Buf, 1, BUFSIZE, stdin)] = 0;
    }

    void flush() {
        fwrite(OBuf, 1, obuf - OBuf, stdout);
    }

    template <class T>
    void read(T &x) {
        x = 0;
        while (!isdigit(*buf)) buf++;
        while (isdigit(*buf)) { x *= 10; x += *buf - '0'; buf++; }
    }

    template <class T>
    void pt(T u) {
		int a[25], *q = a;
		if (!u) *obuf++ = '0';
		else {
			while (u) *q++ = u % 10 + '0' , u /= 10;
			while (q != a) *obuf++ = *--q;
		}
	}

    template <class T>
    void print(T a) {
		pt(a), *obuf++ = '\n';
	}

}
#define read fast_io::read
#define print fast_io::print
const int B = 773;
const int maxn = 6e5 + 5;
struct node{
    int l, r, id, x, y, p;
    bool operator < (const node& x) const{
        if(l/B != x.l/B) return l < x.l;
        return ((l/B)&1) ? (r < x.r) : (r > x.r);
    }
}e[maxn];
int n, q, a[maxn];
vector<int> g[maxn];
int in[maxn],out[maxn], idx=0, dfn[maxn];
int f[maxn][20], dep[maxn];
void dfs(int u, int fa){
    f[u][0] = fa, dep[u]=dep[fa]+1;
    fors(i,0,19) f[u][i+1]=f[f[u][i]][i];
    dfn[in[u]=++idx] = u;
    for(int v: g[u]) if(fa!=v) dfs(v,u);
    dfn[out[u]=++idx] = u;
    return;
}
int lca(int u, int v){
    if(dep[u]<dep[v]) swap(u,v);
    int d = dep[u]-dep[v];fors(i,0,19)if(d>>i&1)u=f[u][i];
    if(u==v) return u;
    for(int i = 19; i >= 0; --i) if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
    return f[u][0];
}
int ex[maxn];
int h[maxn],s=0;
const int BB = 500;
void add(int x){
    h[x]^=1; int id = x/BB;
    (h[x])?++ex[id]:--ex[id];
}
int qry(int l, int r){
    int id1 = l/BB, id2 = r/BB;
    if(id1==id2){
        fors(i,l,r+1) if(h[i]) return i;
        return -1;
    }
    if(ex[id1])fors(i,l,(id1+1)*BB) if(h[i]) return i;
    if(ex[id2])fors(i,id2*BB,r+1) if(h[i]) return i;
    fors(i,id1+1,id2){
        if(!ex[i]) continue;
        fors(j,i*BB,(i+1)*BB) if(h[j]) return j;
    }return -1;
}
int ans[maxn];
int main()
{
    fast_io::init();
    read(n); read(q);
    fors(i,1,n+1) read(a[i]);
    fors(i,1,n){
        int u, v; read(u); read(v); g[u].pb(v); g[v].pb(u);
    }
    dfs(1,0);
    int tot = 0;
    fors(i,0,q){
        int u, v, l, r;
        read(u); read(v); read(l); read(r);
        if(u==v){
            if(l<=a[u] && a[u]<=r) ans[i] = a[u];
            else ans[i] = -1;
        }else {
            if(in[u]>in[v]) swap(u,v);
            int p = lca(u, v);
            if(dep[u]+dep[v]-2*dep[p]<=300){
                int x=u,y=v;
                while(x!=p) add(a[x]),x=f[x][0];
                while(y!=p) add(a[y]),y=f[y][0];
                add(a[p]);
                ans[i] = qry(l, r);
                x=u,y=v;
                while(x!=p) add(a[x]),x=f[x][0];
                while(y!=p) add(a[y]),y=f[y][0];
                add(a[p]);
                continue;
            }
            if(p == u){
                e[tot++] = (node){in[u],in[v],i,l,r,0};
            }else{
                e[tot++] = (node){out[u],in[v],i,l,r,p};
            }
        }
    }
    sort(e,e+tot);
    int lp = 1, rp = 0;
    fors(i,0,tot){
        while(rp<e[i].r) add(a[dfn[++rp]]);
        while(lp>e[i].l) add(a[dfn[--lp]]);
        while(rp>e[i].r) add(a[dfn[rp--]]);
        while(lp<e[i].l) add(a[dfn[lp++]]);
        if(e[i].p) add(a[e[i].p]);
        ans[e[i].id] = qry(e[i].x, e[i].y);
        if(e[i].p) add(a[e[i].p]);
    }
    fors(i,0,q) printf("%d\n", ans[i]);
    fast_io::flush();
	return 0;
}