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 N = 300005;
const int LN = 19;

struct Node {
  long long val;
  Node *l, *r;
  Node(long long _val=0): val(_val) {
    l = r = 0;
  }
  Node(Node *node) {
    val = node->val;
    l = node->l; r = node->r;
  }
};

int n, q;
int c[N];

mt19937_64 rng;
long long h[N];

Node *roots[N];

vector<int> edges[N];
int depth[N];
int par[LN][N];

namespace PersistentSegTree {

Node* build(int l, int r) {
  if (l == r) return new Node();

  int mid = (l + r) >> 1;
  Node *ret = new Node();
  ret->l = build(l, mid + 0);
  ret->r = build(mid + 1, r);
  return ret;
}

Node* update(Node *node, int l, int r, int x, long long val) {
  Node *ret = new Node(node);
  if (l == x && r == x) {
    ret->val ^= val;
    return ret;
  }

  int mid = (l + r) >> 1;
  if (x <= mid) ret->l = update(node->l, l, mid, x, val);
  else ret->r = update(node->r, mid + 1, r, x, val);

  ret->val = ret->l->val ^ ret->r->val;
  return ret;
}

Node *build() {
  return build(0, n - 1);
}

Node *update(Node *node, int x, long long val) {
  return update(node, 0, n - 1, x, val);
}

} // namespace PersistentSegTree

void dfs(int u, int p) {
  par[0][u] = p;
  roots[u] = PersistentSegTree::update(roots[p], c[u], h[c[u]]);
  for (int v : edges[u]) {
    if (v == p) continue;

    depth[v] = depth[u] + 1;
    dfs(v, u);
  }
}

void initLca() {
  for (int i = 1; i < LN; ++i) {
    for (int j = 0; j < n; ++j) {
      par[i][j] = par[i - 1][par[i - 1][j]];
    }
  }
}

int query(Node *u, Node *v, Node *par, Node *ppar, int l, int r, int ll, int rr) {
  int mid = (l + r) >> 1;
  if (l > rr || r < ll) return -1;
  if (l >= ll && r <= rr) {
    if (u->val ^ v->val ^ par->val ^ ppar->val) {
      if (l == r) return l;

      int ret = query(u->l, v->l, par->l, ppar->l, l, mid + 0, ll, rr);
      if (ret != -1) return ret;
      return query(u->r, v->r, par->r, ppar->r, mid + 1, r, ll, rr);
    }
    return -1;
  }

  int ret = query(u->l, v->l, par->l, ppar->l, l, mid, ll, rr);
  if (ret != -1) return ret;
  return query(u->r, v->r, par->r, ppar->r, mid + 1, r, ll, rr);
}

int lca(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  while (depth[u] != depth[v]) u = par[__builtin_ctz(depth[u] - depth[v])][u];

  if (u == v) return u;

  for (int i = LN - 1; i >= 0; --i) {
    if (par[i][u] == par[i][v]) continue;
    u = par[i][u];
    v = par[i][v];
  }
  return par[0][u];
}

int main() {
  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &c[i]);
    --c[i];
  }
  for (int i = 1; i < n; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    --u, --v;

    edges[u].push_back(v);
    edges[v].push_back(u);
  }

  for (int i = 0; i < n; ++i) h[i] = rng();

  par[0][0] = n;
  roots[n] = PersistentSegTree::build();
  dfs(0, n);
  initLca();

  while (q--) {
    int u, v, l, r;
    scanf("%d %d %d %d", &u, &v, &l, &r);
    --u, --v, --l, --r;

    int p = lca(u, v);
    int res = query(roots[u], roots[v], roots[p], roots[par[0][p]], 0, n - 1, l, r);
    printf("%d\n", res == -1 ? -1 : res + 1);
  }
  return 0;
}