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:
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

const int mod[2] = {(int) 1e9 + 7, (int) 1e9 + 9};

struct Hash {
  static const int n = 2;
  int a[n];

  Hash() {
    for (int i = 0; i < n; ++i) {
      a[i] = 0;
    }
  }
  
  Hash(int x) {
    for (int i = 0; i < n; ++i) {
      a[i] = x % mod[i];
    }
  }

  Hash operator + (const Hash &h) const {
    Hash res;
    for (int i = 0; i < n; ++i) {
      res.a[i] = a[i] + h.a[i];
      if (res.a[i] >= mod[i]) {
        res.a[i] -= mod[i];
      }
    }
    return res;
  }

  Hash operator - (const Hash &h) const {
    Hash res;
    for (int i = 0; i < n; ++i) {
      res.a[i] = a[i] - h.a[i];
      if (res.a[i] < 0) {
        res.a[i] += mod[i];
      }
    }
    return res;
  }

  Hash operator * (const Hash &h) const {
    Hash res;
    for (int i = 0; i < n; ++i) {
      res.a[i] = (long long) a[i] * h.a[i] % mod[i];
    }
    return res;
  }

  bool operator == (const Hash &h) const {
    for (int i = 0; i < n; ++i) {
      if (a[i] != h.a[i]) {
        return false;
      }
    }
    return true;
  }

  bool operator != (const Hash &h) const {
    for (int i = 0; i < n; ++i) {
      if (a[i] != h.a[i]) {
        return true;
      }
    }
    return false;
  }
};

const int maxn = (int) 6e5 + 5;
Hash pws[maxn];

struct T {
  Hash h;
  int len;

  T(): h(), len(0) {}

  T(int x): h(x), len(1) {}

  T(const Hash &h, int len): h(h), len(len) {}

  T operator + (const T &t) const {
    return T(h * pws[t.len] + t.h, len + t.len);
  }

  bool operator == (const T &t) const {
    return h == t.h && len == t.len;
  }

  bool operator != (const T &t) const {
    return h != t.h || len != t.len;
  }
};

void precalc() {
  pws[0] = Hash(1);
  pws[1].a[0] = rnd(mod[0]);
  pws[1].a[1] = rnd(mod[1]);
  for (int i = 2; i < maxn; ++i) {
    pws[i] = pws[i - 1] * pws[1];
  }
}

int n, q;
int a[maxn];
vector<int> g[maxn];

bool read() {
  if (scanf("%d%d", &n, &q) < 2) {
    return false;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    --a[i];
  }
  for (int i = 0; i < n; ++i) {
    g[i].clear();
  }
  for (int i = 0; i < n - 1; ++i) {
    int v, u;
    scanf("%d%d", &v, &u);
    --v;
    --u;
    g[v].push_back(u);
    g[u].push_back(v);
  }
  return true;
}

const int logn = 20;
int ps[maxn][logn];
int ls[maxn], rs[maxn];
vector<int> p;

void dfs(int v, int pr) {
  ps[v][0] = (pr == -1 ? v : pr);
  for (int i = 1; i < logn; ++i) {
    ps[v][i] = ps[ps[v][i - 1]][i - 1];
  }
  ls[v] = sz(p);
  p.push_back(a[v]);
  for (int i = 0; i < sz(g[v]); ++i) {
    int u = g[v][i];
    if (u == pr) {
      continue;
    }
    dfs(u, v);
  }
  rs[v] = sz(p);
  p.push_back(a[v]);
}

bool anc(int v, int u) {
  return ls[v] <= ls[u] && rs[u] <= rs[v];
}

int getLca(int v, int u) {
  if (anc(v, u)) {
    return v;
  }
  if (anc(u, v)) {
    return u;
  }
  for (int i = logn - 1; i >= 0; --i) {
    if (!anc(ps[v][i], u)) {
      v = ps[v][i];
    }
  }
  return ps[v][0];
}

struct node {
  T val;
  node *l, *r;

  node(const T &val): val(val), l(0), r(0) {}

  node(node *ll, node *rr): val(ll->val + rr->val), l(ll), r(rr) {}
};

node *buildst(int l, int r) {
  if (l == r - 1) {
    return new node(T(0));
  }
  int m = (l + r) / 2;
  node *vl = buildst(l, m);
  node *vr = buildst(m, r);
  return new node(vl, vr);
}

node *update(node *v, int l, int r, int pos, int val) {
  if (l == r - 1) {
    return new node(T(val));
  }
  int m = (l + r) / 2;
  if (pos < m) {
    return new node(update(v->l, l, m, pos, val), v->r);
  } else {
    return new node(v->l, update(v->r, m, r, pos, val));
  }
}

int get(node *v, node *u, int tl, int tr, int l, int r) {
  if (l == tl && r == tr) {
    if (v->val == u->val) {
      return -1;
    }
    if (l == r - 1) {
      return l;
    }
    int m = (l + r) / 2;
    if (v->l->val != u->l->val) {
      return get(v->l, u->l, l, m, l, m);
    } else {
      return get(v->r, u->r, m, r, m, r);
    }
  }
  int tm = (tl + tr) / 2;
  if (l >= tm) {
    return get(v->r, u->r, tm, tr, l, r);
  }
  if (r <= tm) {
    return get(v->l, u->l, tl, tm, l, r);
  }
  int res = get(v->l, u->l, tl, tm, l, tm);
  if (res == -1) {
    res = get(v->r, u->r, tm, tr, tm, r);
  }
  return res;
}

node *st[maxn];

int getRes(int v, int u, int l, int r) {
  if (rs[v] > rs[u]) {
    swap(v, u);
  }
  int ll = rs[v], rr = rs[u];
  return get(st[ll], st[rr], 0, n, l, r);
}

int cnt[maxn];

void solve() {
  p.clear();
  dfs(0, -1);
  st[0] = buildst(0, n);
  for (int i = 0; i < n; ++i) {
    cnt[i] = 0;
  }
  for (int i = 0; i < sz(p); ++i) {
    cnt[p[i]] ^= 1;
    st[i + 1] = update(st[i], 0, n, p[i], cnt[p[i]]);
  }
  for (int qq = 0; qq < q; ++qq) {
    int v, u, l, r;
    scanf("%d%d%d%d", &v, &u, &l, &r);
    --v;
    --u;
    --l;
    int w = getLca(v, u);
    int x = a[w];
    int res = -1;
    if (x < l || x >= r) {
      res = getRes(v, u, l, r);
    } else {
      if (getRes(v, u, x, x + 1) == -1) {
        res = x;
      } else {
        if (l < x) {
          res = getRes(v, u, l, x);
        }
        if (x + 1 < r && res == -1) {
          res = getRes(v, u, x + 1, r);
        }
      }
    }
    if (res >= 0) {
      ++res;
    }
    printf("%d\n", res);
  }
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}