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 c=300002, gy=600, k=20;
int n, q, t[c];
int cnt, be[c], ki[c], sor[2*c], szint[c], fel[c][k];
int csop[gy], ll=1, rr, oszt[c], gyoszt[c], ans[c];
int kezd[c], veg[c], kis[c], nagy[c], spec[c];
vector<int> sz[c];
bool v[c], db[c];
vector<pair<long long, int> > mo;
void dfs(int a) {
    cnt++;
    be[a]=cnt;
    sor[cnt]=a;
    v[a]=true;
    for (int i=1; i<k; i++) {
        fel[a][i]=fel[fel[a][i-1]][i-1];
    }
    for (int x:sz[a]) {
        if (!v[x]) {
            szint[x]=szint[a]+1;
            fel[x][0]=a;
            dfs(x);
        }
    }
    cnt++;
    ki[a]=cnt;
    sor[cnt]=a;
}
int lca(int a, int b) {
    if (szint[a]<szint[b]) {
        swap(a, b);
    }
    for (int i=k-1; i>=0; i--) {
        if (szint[fel[a][i]]>=szint[b]) {
            a=fel[a][i];
        }
    }
    for (int i=k-1; i>=0; i--) {
        if (fel[a][i]!=fel[b][i]) {
            a=fel[a][i], b=fel[b][i];
        }
    }
    if (a!=b) {
        a=fel[a][0];
    }
    return a;
}
void add(int a) {
    int ert=t[sor[a]];
    db[ert]=!db[ert];
    if (db[ert]) {
        csop[gyoszt[ert]]++;
    } else {
        csop[gyoszt[ert]]--;
    }
}
long long gilbertOrder(int x, int y, int pow, int rotate) {
	if (pow == 0) {
		return 0;
	}
	int hpow = 1 << (pow-1);
	int seg = (x < hpow) ? (
		(y < hpow) ? 0 : 3
	) : (
		(y < hpow) ? 1 : 2
	);
	seg = (seg + rotate) & 3;
	const int rotateDelta[4] = {3, 0, 0, 1};
	int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
	int nrot = (rotate + rotateDelta[seg]) & 3;
	int64_t subSquareSize = int64_t(1) << (2*pow - 2);
	long long ans = seg * subSquareSize;
	int64_t add = gilbertOrder(nx, ny, pow-1, nrot);
	ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
	return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> q;
    for (int i=gy; i<=n; i+=gy) {
        oszt[i]=i/gy;
    }
    for (int i=1; i<=n; i++) {
        gyoszt[i]=i/gy;
    }
    for (int i=1; i<=n; i++) {
        cin >> t[i];
    }
    for (int i=1; i<n; i++) {
        int a, b; cin >> a >> b;
        sz[a].push_back(b), sz[b].push_back(a);
    }
    szint[1]=1;
    dfs(1);
    for (int i=1; i<=q; i++) {
        int a, b, c, d, s;
        cin >> a >> b >> c >> d;
        if (be[a]>be[b]) {
            swap(a, b);
        }
        s=lca(a, b);
        if (a==s) {
            a=be[a], b=be[b];
        } else {
            a=ki[a], b=be[b];
            spec[i]=s;
        }
        kezd[i]=a, veg[i]=b, kis[i]=c, nagy[i]=d;
        long long ert=gilbertOrder(a, b, 20, 0);
        mo.push_back({ert, i});
    }
    sort(mo.begin(), mo.end());
    for (int i=0; i<q; i++) {
        int id=mo[i].second;
        int bb=kezd[id], jj=veg[id];
        while (ll>bb) {
            add(--ll);
        }
        while (ll<bb) {
            add(ll++);
        }
        while (rr<jj) {
            add(++rr);
        }
        while (rr>jj) {
            add(rr--);
        }
        add(be[spec[id]]);
        int valasz=0, bal=kis[id], jobb=nagy[id];
        while (bal<=jobb) {
            if (oszt[bal] && !csop[oszt[bal]]) {
                bal+=gy;
            } else {
                if (db[bal]) {
                    valasz=bal;
                    break;
                }
                bal++;
            }
        }
        if (!valasz) {
            valasz=-1;
        }
        ans[id]=valasz;

        add(be[spec[id]]);
    }
    for (int i=1; i<=q; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}