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;

typedef long long ll;
typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i < int(b); i++)
#define FORD(i, a, b) for (int i = (b)-1; i >= int(a); i--)
#define sz(c) int((c).size())
#define all(c) c.begin(), c.end()
#define debug(x) cerr << #x << ": " << x << endl;

const int MAXN = 300005;
const int bucketSize = 765;
const int MAX_BUCKET = 1 + (2*MAXN) / bucketSize;
int a[MAXN];

struct Query {
  int u, v, l, r;
  int idx;
};

vector<Query> vq[MAX_BUCKET];

struct SparseTable {
  vector<vector<int>> ST;
  vector<int> P;
  int N;
  int MAXLOG = 0;

  void build(int n, const vector<int> &V) {
    N = n;
    while ((1 << MAXLOG) <= N)
      ++MAXLOG;
    ST = vector<vector<int>>(N, vector<int>(MAXLOG));
    P = vector<int>(N + 1);
    int LOG = 0;
    for (int i = 1; i < N + 1; ++i) {
      if (1 << (LOG + 1) <= i)
        P[i] = ++LOG;
      else
        P[i] = LOG;
    }
    // Dynamic Sparse table building
    for (int i = 0; i < N; ++i) {
      ST[i][0] = i;
    }
    for (int j = 1; j < MAXLOG; ++j) {
      for (int i = 0; i + (1 << j) - 1 < N; ++i) {
        if (V[ST[i][j - 1]] < V[ST[i + (1 << (j - 1))][j - 1]])
          ST[i][j] = ST[i][j - 1];
        else
          ST[i][j] = ST[i + (1 << (j - 1))][j - 1];
      }
    }
  }

  int query(int l, int r, const vector<int> &V) {
    int LOG = P[r - l + 1];

    if (V[ST[l][LOG]] < V[ST[r - (1 << LOG) + 1][LOG]])
      return ST[l][LOG];
    return ST[r - (1 << LOG) + 1][LOG];
  }
};

struct Tree {
  vector<vector<int>> adj;
  int V, E;
  int LOG;
  int cnt = 0;
  vi tin, tout, inOutTour;
  vector<int> Eulerian_tour, RMQ_reduction, Ocurrence;
  SparseTable S;

  void Eulerian_dfs(int p, int u, int depth) {
    if (Ocurrence[u] == -1)
      Ocurrence[u] = sz(Eulerian_tour);
    tin[u] = cnt++;
    inOutTour.push_back(u);
    Eulerian_tour.push_back(u);
    RMQ_reduction.push_back(depth);
    for (int v : adj[u]) {
      if (v != p) {
        Eulerian_dfs(u, v, depth + 1);
        Eulerian_tour.push_back(u);
        RMQ_reduction.push_back(depth);
      }
    }
    inOutTour.push_back(u);
    tout[u] = cnt++;
  }

  void build(int n) {
    V = n;
    E = n - 1;
    adj.resize(V);
    tin.resize(V);
    tout.resize(V);
    Ocurrence = vector<int>(V, -1);
    for (int i = 0; i < E; ++i) {
      int x, y;
      cin >> x >> y; // we suppose nodes are 0-indexed
      --x, --y;
      adj[x].push_back(y);
      adj[y].push_back(x);
    }
    Eulerian_dfs(0, 0, 0);
    S.build(sz(RMQ_reduction), RMQ_reduction);
  }

  int query(int l, int r) {
    int L = min(Ocurrence[l], Ocurrence[r]);
    int R = max(Ocurrence[l], Ocurrence[r]);
    return Eulerian_tour[S.query(L, R, RMQ_reduction)];
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  auto curT = clock();
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
  }
  Tree t;
  t.build(n);
  if(n == 300000)
    cerr << (double)(clock() - curT) /
      (CLOCKS_PER_SEC);
  vector<int> ans(q, -1337);
  for (int i = 0; i < q; ++i) {
    int u, v, l, r;
    cin >> u >> v >> l >> r;
    --u, --v;
    --l, --r;
    if (t.tin[u] > t.tin[v])
      swap(u, v);
    int qleft = (t.query(u, v) == u ? t.tin[u] : t.tout[u]);
    vq[qleft / bucketSize].push_back({u, v, l, r, i});
  }
  for (int i = 0; i < MAX_BUCKET; ++i) {
    sort(vq[i].begin(), vq[i].end(), [&t](const Query &q1, const Query &q2) {
      return t.tin[q1.v] < t.tin[q2.v];
    });
    int lft = -1;
    int rgt = -1;
    vi oddSum(MAX_BUCKET, 0);
    vi color(n, 0);
    vi status(n, 0);
    for (Query j : vq[i]) {
      int lca = t.query(j.u, j.v);
      int targetLft = t.tin[j.u];
      int targetRgt = t.tin[j.v];
      if (lca != j.u) {
        targetLft = t.tout[j.u];
        color[a[lca]]++;
        if (color[a[lca]] & 1)
          oddSum[a[lca] / bucketSize]++;
        else
          oddSum[a[lca] / bucketSize]--;
      }
      if (lft == -1)
        lft = targetLft, rgt = targetLft - 1;
      int curNode = -1;
      while (lft < targetLft) {
        curNode = t.inOutTour[lft++];
        --status[curNode];
        (status[curNode] & 1 ? ++color[a[curNode]] : --color[a[curNode]]);
        ((color[a[curNode]] & 1) ? oddSum[a[curNode] / bucketSize]++
                                 : oddSum[a[curNode] / bucketSize]--);
      }
      while (lft > targetLft) {
        curNode = t.inOutTour[--lft];
        ++status[curNode];
        (status[curNode] & 1 ? ++color[a[curNode]] : --color[a[curNode]]);
        ((color[a[curNode]] & 1) ? oddSum[a[curNode] / bucketSize]++
                                 : oddSum[a[curNode] / bucketSize]--);
      }
      while (rgt < targetRgt) {
        curNode = t.inOutTour[++rgt];
        ++status[curNode];
        (status[curNode] & 1 ? ++color[a[curNode]] : --color[a[curNode]]);
        ((color[a[curNode]] & 1) ? oddSum[a[curNode] / bucketSize]++
                                 : oddSum[a[curNode] / bucketSize]--);
      }
      while (rgt > targetRgt) {
        curNode = t.inOutTour[rgt--];
        --status[curNode];
        (status[curNode] & 1 ? ++color[a[curNode]] : --color[a[curNode]]);
        ((color[a[curNode]] & 1) ? oddSum[a[curNode] / bucketSize]++
                                 : oddSum[a[curNode] / bucketSize]--);
      }
      int curAns = -2;
      for (int k = 0; curAns == -2 && k < MAX_BUCKET; ++k) {
        int lLimit = bucketSize * k;
        if (lLimit >= n)
          break;
        int rLimit = min(n - 1, bucketSize * (k + 1));

        // totally out
        if (lLimit > j.r || rLimit < j.l)
          continue;
        // totally in
        if (lLimit >= j.l && rLimit <= j.r) {
          // check odd_sum!
          if (oddSum[k]) {
            for (int kk = lLimit; kk <= rLimit; ++kk) {
              if (color[kk] & 1)
                curAns = kk;
            }
          }
        }
        // partially out
        else if (lLimit >= j.l) {
          for (int kk = lLimit; kk <= j.r; ++kk) {
            if (color[kk] & 1)
              curAns = kk;
          }
          // lLimit to j.r
        } else if (rLimit <= j.r) {
          for (int kk = j.l; kk <= rLimit; ++kk) {
            if (color[kk] & 1)
              curAns = kk;
          }
          // j.l to rLimit
        }
        // If the bucket is not outside, not inside and not partial. It means
        // that the other interval is inside??
        else if (j.l >= lLimit && j.r <= rLimit) {
          for (int kk = j.l; kk <= j.r; ++kk) {
            if (color[kk] & 1)
              curAns = kk;
          }
        }
      }
      ans[j.idx] = curAns;
      if (lca != j.u) {
        color[a[lca]]--;
        ((color[a[lca]] & 1) ? oddSum[a[lca] / bucketSize]++
                                 : oddSum[a[lca] / bucketSize]--);
      }
    }
  }
  for (int i : ans) {
    cout << i + 1 << '\n';
  }
}

/*
Things to maintain:
colorToNumber[color] -> number of color appereance
colorToNumberCompressed[color / bucketSize] -> number of odd colors

Mo's
IteratorToNode[iterator] -> Node
NodeToColor[Node] -> Color

NodeToIterator[Node] -> Iterator

 */