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;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T>
T rand(T a, T b) {
    return uniform_int_distribution<T>(a, b)(rng);
}


const int maxn = 3e5+10;
const int LOG = 19; //2^19 > 5e5


int n, q;
vector<int> g[maxn];
ll A[maxn];
ll H[maxn];

struct node {
    ll val;
    node *left;
    node *right;
    node (ll v) {
	val = v;
	left=right=NULL;
    }
    node (node *l, node *r) {
	left=l;
	right=r;
	val=(left->val^right->val);
    }
};

node *t[maxn];

node *build(int tl, int tr) {
    if (tl==tr) {
	return new node(0);
    } else {
	int tm=(tl+tr)/2;
	return new node(build(tl,tm), build(tm+1,tr));
    }
}

node *upd(node *p, int tl, int tr, int i) {
    if (tl==tr) {
	return new node(p->val^H[i]);
    } else {
	int tm=(tl+tr)/2;
	if (i<=tm) {
	    return new node(upd(p->left,tl,tm,i), p->right);
	} else {
	    return new node(p->left, upd(p->right,tm+1,tr,i));
	}
    }
}

ll qry(node *a, node *b, int tl, int tr, int l, int r) {
    if (l>r) {
	return -1;
    }
    if (a->val==b->val) {
	return -1;
    }
    if (tl==tr) {
	return tl;
    }
    int tm=(tl+tr)/2;
    ll left = qry(a->left, b->left, tl, tm, l, min(tm,r));
    if (~left) return left;
    return qry(a->right, b->right, tm+1, tr, max(tm+1,l), r);
}

int dep[maxn];
int par[LOG+1][maxn];

void dfs(int at, int p) {
    for (int j=1; j<=LOG; j++) {
	par[j][at]=par[j-1][par[j-1][at]];
    }
    
    t[at]=upd(t[p],1,n,A[at]);
	
    for (int to: g[at]) {
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to]=at;
	dfs(to, at);
    }
}

int lca(int u, int v) {
    if (dep[u]<dep[v]) {
	swap(u,v);
    }
    int dx=dep[u]-dep[v];
    for (int j=0; j<=LOG; j++) {
	if (dx>>j&1) {
	    u=par[j][u];
	}
    }
    if (u==v) {
	return u;
    }
    for (int j=LOG; j>=0; j--) {
	if (par[j][u]!=par[j][v]) {
	    u = par[j][u];
	    v = par[j][v];
	}
    }
    return par[0][v];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>q;
    for (int i=1; i<=n; i++) {
	cin>>A[i];
    }
    
    for (int i=1; i<=n; i++) {
	H[i] = rand(1ll,1ll<<61);
    }
    
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    t[0] = build(1,n);
    dfs(1, 0);



    while (q--) {
	int u,v,l,r;
	cin>>u>>v>>l>>r;
	node *tmp = upd(t[v],1,n,A[lca(u,v)]);
	cout<<qry(t[u],tmp,1,n,l,r)<<"\n";
    }
    
    return 0;
}