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:
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
#define BU 775
int l[300005],stt[300005],ent[300005],ans[300005],cnt[300005],bl[BU],dp[20][300005],dep[300005];
vector<int> v[300005],e;
void dfs(int node,int p)
{
	stt[node]=e.size();
	e.push_back(l[node]);
	dp[0][node]=p;
	for (int i=1;i<20;i++)
	dp[i][node]=dp[i-1][dp[i-1][node]];
	dep[node]=dep[p]+1;
	for (int u:v[node])
	{
		if (u!=p)
		dfs(u,node);
	}
	ent[node]=e.size();
	e.push_back(l[node]);
}
int lca(int u,int v)
{
	if (dep[u]<dep[v])
	swap(u,v);
	int dist=dep[u]-dep[v];
	for (int i=0;i<20;i++)
	{
		if (dist&(1<<i))
		u=dp[i][u];
	}
	if (u==v)
	return u;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][u]!=dp[i][v])
		{
			v=dp[i][v];
			u=dp[i][u];
		}
	}
	return dp[0][u];
}
struct query
{
	int u,v,l,r,lo,ro,i;
	bool f;
	query(int uu,int vv,int ii,int ll,int rr)
	{
		u=uu;
		v=vv;
		i=ii;
		lo=ll;
		ro=rr;
		if (stt[u]>stt[v])
		swap(u,v);
		r=stt[v];
		if (lca(u,v)==u)
		{
			l=stt[u];
			f=0;
		}
		else
		{
			l=ent[u];
			f=1;
		}
	}
	bool operator<(const query &q) const
	{
		if (l/BU==q.l/BU)
		return (r<q.r);
		return (l<q.l);
	}
};
void upd(int i)
{
	i=e[i];
	bl[i/BU]-=cnt[i];
	cnt[i]^=1;
	bl[i/BU]+=cnt[i];
}
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
	scanf("%d",&l[i]);
	for (int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,0);
	vector<query> qu;
	for (int i=0;i<q;i++)
	{
		int a,b,l,r;
		scanf("%d%d%d%d",&a,&b,&l,&r);
		qu.push_back(query(a,b,i,l,r));
		ans[i]=-1;
	}
	sort(qu.begin(),qu.end());
	int cl=0,cr=-1;
	for (auto c:qu)
	{
		while (cl>c.l)
		upd(--cl);
		while (cr<c.r)
		upd(++cr);
		while (cl<c.l)
		upd(cl++);
		while (cr>c.r)
		upd(cr--);
		if (c.f)
		upd(stt[lca(c.u,c.v)]);
		int cur=c.lo;
		while (cur<=c.ro && cur%BU)
		{
			if (cnt[cur])
			ans[c.i]=cur;
			cur++;
		}
		while (cur+BU-1<=c.ro)
		{
			if (bl[cur/BU])
			{
				while (!cnt[cur])
				cur++;
				ans[c.i]=cur;
				break;
			}
			cur+=BU;
		}
		if (ans[c.i]==-1)
		{
			while (cur<=c.ro)
			{
				if (cnt[cur])
				ans[c.i]=cur;
				cur++;
			}
		}
		if (c.f)
		upd(stt[lca(c.u,c.v)]);
	}
	for (int i=0;i<q;i++)
	printf("%d\n",ans[i]);
}