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 ull unsigned long long
using namespace std;

const int N = 3e5 + 5;

namespace FastIO {
  const int SIZE=1<<16; char buf[SIZE], obuf[SIZE], str[64]; int bi=SIZE, bn=SIZE, opt;
  int read(char *s) {
    while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
    int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
  }
  bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n)return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
  void write(int x) {
    if(!x) obuf[opt++] = '0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
    if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}
  }
  void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}}
  void Fflush() { if (opt) fwrite(obuf, 1, opt, stdout); opt=0;}
} using namespace FastIO;

mt19937_64 rng(2021);

int n, q, a[N], fa[N], dep[N], siz[N], son[N], top[N], tot, rt[N], ls[N * 25], rs[N * 25];
ull w[N], val[N * 25];
vector<int> g[N];

int modify(int p, int l, int r, int x, ull k) {
  int np = ++tot;
  if (l == r) {
    val[np] = val[p] ^ k;
    return np;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) {
    ls[np] = modify(ls[p], l, mid, x, k);
    rs[np] = rs[p];
  } else {
    ls[np] = ls[p];
    rs[np] = modify(rs[p], mid + 1, r, x, k);
  }
  val[np] = val[ls[np]] ^ val[rs[np]];
  return np;
}

void dfs(int u) {
  siz[u] = 1;
  rt[u] = modify(rt[fa[u]], 1, n, a[u], w[a[u]]);
  for (auto v : g[u]) if (v != fa[u]) {
    fa[v] = u, dep[v] = dep[u] + 1;
    dfs(v), siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}

void dfs2(int u, int topf) {
  top[u] = topf;
  if (son[u]) dfs2(son[u], topf);
  for (auto v : g[u]) if (v != fa[u] && v != son[u]) dfs2(v, v);
}

int Lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] < dep[top[v]]) swap(u, v);
    u = fa[top[u]];
  }
  return dep[u] < dep[v] ? u : v;
}

ull calc(int p, int q, int lca, int l, int r) {
  return val[p] ^ val[q] ^ ((l <= a[lca] && a[lca] <= r) ? w[a[lca]] : 0);
}

int query(int p, int q, int lca, int l, int r, int x, int y) {
  if (x <= l && r <= y) {
    if ((val[p] ^ val[q] ^ ((l <= a[lca] && a[lca] <= r) ? w[a[lca]] : 0)) == 0ull) {
      return -1;
    }
  }
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (x <= mid) {
    int res = query(ls[p], ls[q], lca, l, mid, x, y);
    if (res != -1) {
      return res;
    }
  }
  if (y > mid) {
    int res = query(rs[p], rs[q], lca, mid + 1, r, x, y);
    if (res != -1) return res;
  }
  return -1;
}

int main() {
  srand(time(0));
  read(n), read(q);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) w[i] = rng();
  for (int i = 1, u, v; i < n; i++) {
    read(u), read(v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1), dfs2(1, 1);
  while (q--) {
    int u, v, l, r;
    read(u), read(v), read(l), read(r);
    write(query(rt[u], rt[v], Lca(u, v), 1, n, l, r));
    write('\n');
  }
  return Fflush(), 0;
}