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 B = 650;
const int N = 300010;

vector <int> g[N];
tuple <int, int, int, int> queries[N];
int qu[N], qv[N], qlca[N], ql[N], qr[N], ans[N], good[N], goodSum[N];
int n, q, a[N], p[N], h[N], jump[N], flat[N << 1], in[N], out[N], ptr;

void go (int u = 1, int par = -1) {
  flat[++ptr] = u, in[u] = ptr;
  for (int v : g[u]) if (v ^ par) {
    p[v] = u, h[v] = h[u] + 1;
    int x = jump[u], y = jump[x];
    jump[v] = (h[u] + h[y] == h[x] + h[x]) ? y : u;
    go(v, u);
  }
  flat[++ptr] = u, out[u] = ptr;
}

int lca (int u, int v) {
  if (h[u] < h[v]) swap(u, v);
  while (h[u] > h[v]) u = h[jump[u]] < h[v] ? p[u] : jump[u];
  while (u ^ v) (jump[u] ^ jump[v]) ? (u = jump[u], v = jump[v]) : (u = p[u], v = p[v]);
  return u;
}

inline void add (int c) {
  good[c] ? --goodSum[c / B] : ++goodSum[c / B], good[c] ^= 1;
}

int query (int l, int r) {
  int lb = l / B, rb = r / B;
  if (lb == rb) {
    for (int i = l; i <= r; ++i) if (good[i]) return i;
    return -1;
  }
  int st = (lb + 1) * B, en = rb * B;
  for (int i = l; i < st; ++i) if (good[i]) return i;
  for (int i = en; i <= r; ++i) if (good[i]) return i;
  for (int blk = lb + 1; blk < rb; ++blk) if (goodSum[blk]) {
    for (int i = blk * B; i < blk * B + B; ++i) if (good[i]) return i;
  }
  return -1;
}

int main() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
  }
  for (int i = 1, u, v; i < n; ++i) {
    scanf("%d %d", &u, &v);
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  p[1] = -1, jump[1] = 1; go();
  for (int i = 1; i <= q; ++i) {
    int u, v, l, r;
    scanf("%d %d %d %d", &u, &v, &l, &r);
    if (in[u] > in[v]) swap(u, v);
    int root = lca(u, v);
    ql[i] = l, qr[i] = r, qu[i] = u, qv[i] = v, qlca[i] = root;
    if (u == root) queries[i] = make_tuple(in[u] / B, in[v], in[u], i);
    else queries[i] = make_tuple(out[u] / B, in[v], out[u], i);
  }
  for (int i = 1; i <= ptr; ++i) flat[i] = a[flat[i]];
  sort(queries + 1, queries + q + 1);
  int L = 1, R = 0;
  for (int i = 1; i <= q; ++i) {
    auto [blockID, rt, lt, idx] = queries[i];
    while (R < rt) add(flat[++R]);
    while (L > lt) add(flat[--L]);
    while (L < lt) add(flat[L++]);
    while (R > rt) add(flat[R--]);
    if (qlca[idx] != qu[idx]) add(flat[in[qlca[idx]]]);
    ans[idx] = query(ql[idx], qr[idx]);
    if (qlca[idx] != qu[idx]) add(flat[in[qlca[idx]]]);
  }
  for (int i = 1; i <= q; ++i) printf("%d\n", ans[i]);
  return 0;
}