#include <bits/stdc++.h>
using namespace std;
const unsigned short NIL = (unsigned short)(-1);
unsigned short n, arr[50000], iparent[50000][9], depth[50000], qna[50000],
    qnb[50000], nb, nbx, mk, mkb;
long q;
vector<unsigned short> edges[50000];
vector<pair<unsigned short, long>> queriea[50000];
vector<pair<unsigned short, long>> querieb[50000];
void dfs(unsigned short i, unsigned short p, unsigned short d) {
  iparent[i][0] = p, depth[i] = d;
  for (unsigned short l = 0; l + 1 < 9 && iparent[i][l] != NIL; l++)
    iparent[i][l + 1] = iparent[iparent[i][l]][l];
  for (unsigned short j = 0; j < edges[i].size(); j++)
    if (edges[i][j] != p) dfs(edges[i][j], i, d + 1);
}
unsigned short swap_bits(unsigned short x) {
  return ((x & nbx) << mkb) + (x >> mkb);
}
void search(long iq, unsigned short du, unsigned short v) {
  unsigned short st = 0;
  for (; depth[v] - du >= nb; st += nb, v = iparent[v][mkb])
    querieb[v].push_back(make_pair(st, iq));
  queriea[v].push_back(make_pair(swap_bits(depth[v] - du + st), iq));
}
void pre_search(unsigned short du, unsigned short v) {
  for (; depth[v] - du >= nb; qnb[v]++, v = iparent[v][mkb])
    ;
  qna[v]++;
}
struct TRIE {
  unsigned short *data, nr, *arx, k;
  long kl, ml;
  TRIE(unsigned short mk) {
    k = mk, ml = 1 << k;
    arx = (unsigned short *)malloc(nb * sizeof(unsigned short));
    kl = (1 << (k + 1)) - 1;
    data = (unsigned short *)malloc(kl * sizeof(unsigned short));
    memset(data, 0, kl * sizeof(unsigned short));
  }
  void init(unsigned short j) {
    for (unsigned short l = 0; l < nb && j != NIL; l++, j = iparent[j][0])
      arx[l] = arr[j] ^ l;
    nr = 0;
  }
  void end() {
    for (unsigned short rr = 0; rr < nr; rr++)
      for (long l = arx[rr]; l != kl && data[l] != 0; l = (l >> 1) ^ ml)
        data[l] = 0;
  }
  ~TRIE() {
    free(data);
    free(arx);
  }
  unsigned short query(unsigned short r, unsigned short high) {
    for (; nr < r; nr++)
      for (long l = arx[nr], p = l + 1; l != kl; l = (l >> 1) ^ ml)
        data[l] = max(data[l], (unsigned short)p);
    unsigned short ans = 0;
    for (long l = kl ^ 3, mask = ml >> 1; mask != 0; mask >>= 1) {
      unsigned short u = ((high & mask) == 0), x = (data[l ^ u] != 0);
      ans = (ans << 1) ^ x;
      if ((high & (mask - 1)) == 0)
        return ((data[l ^ u ^ x ^ 1] - 1) & (mask - 1)) + ans * mask;
      else
        l = ((l ^ u ^ x ^ 1) << 1) & kl;
    }
    return ans;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  unsigned short u, v;
  long m;
  cin >> n >> q;
  for (unsigned short i = 0; i < n; i++) cin >> arr[i];
  for (unsigned short i = 0; i < n - 1; i++) {
    cin >> u >> v;
    u--, v--;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  memset(iparent, NIL, sizeof(iparent));
  dfs(0, NIL, 0);
  for (m = 1, mk = 0; m < n; m <<= 1, mk++)
    ;
  mkb = (mk & 1) ? 1 + (mk >> 1) : (mk >> 1);
  nb = 1 << mkb;
  nbx = nb - 1;
  if (m == n) mk++;
  unsigned short qans[q];
  memset(qans, 0, q * sizeof(unsigned short));
  unsigned short *qu = new unsigned short[q], *qv = new unsigned short[q];
  for (long i = 0; i < q; i++) {
    cin >> u >> v;
    pre_search(qu[i] = depth[u - 1], qv[i] = v - 1);
  }
  for (unsigned short i = 0; i < n; i++) {
    queriea[i].reserve(qna[i]);
    querieb[i].reserve(qnb[i]);
  }
  for (long i = 0; i < q; i++) search(i, qu[i], qv[i]);
  delete[] qu, delete[] qv;
  TRIE trie(mk);
  for (unsigned short i = 0; i < n; i++) {
    if (queriea[i].size() == 0 && querieb[i].size() == 0) continue;
    sort(queriea[i].begin(), queriea[i].end());
    trie.init(i);
    unsigned short imax = 0, pre = NIL, ipre;
    for (auto &jr : {queriea, querieb}) {
      pre = NIL;
      for (auto &j : jr[i]) {
        unsigned short &iaft = qans[j.second];
        ipre = j.first;
        if (pre != ipre) {
          pre = ipre;
          imax = jr == querieb
                     ? trie.query(nb, pre)
                     : trie.query((pre >> mkb) + 1, (pre & nbx) << mkb);
        }
        if (imax > iaft) iaft = imax;
      }
    }
    trie.end();
  }
  for (long i = 0; i < q; i++) cout << qans[i] << endl;
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

Lech got into a tree consisting of n vertices with a root in vertex number 1. At each vertex i written integer ai. He will not get out until he answers q queries of the form u v. Answer for the query is maximal value <image> among all vertices i on path from u to v including u and v, where dist(i, v) is number of edges on path from i to v. Also guaranteed that vertex u is ancestor of vertex v. Leha's tastes are very singular: he believes that vertex is ancestor of itself.

Help Leha to get out.

The expression <image> means the bitwise exclusive OR to the numbers x and y.

Note that vertex u is ancestor of vertex v if vertex u lies on the path from root to the vertex v.

Input

First line of input data contains two integers n and q (1 ≤ n ≤ 5·104, 1 ≤ q ≤ 150 000) — number of vertices in the tree and number of queries respectively.

Next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ n) — numbers on vertices.

Each of next n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n) — description of the edges in tree.

Guaranteed that given graph is a tree.

Each of next q lines contains two integers u and v (1 ≤ u, v ≤ n) — description of queries. Guaranteed that vertex u is ancestor of vertex v.

Output

Output q lines — answers for a queries.

Examples

Input

5 3
0 3 2 1 4
1 2
2 3
3 4
3 5
1 4
1 5
2 4


Output

3
4
3


Input

5 4
1 2 3 4 5
1 2
2 3
3 4
4 5
1 5
2 5
1 4
3 3


Output

5
5
4
3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const unsigned short NIL = (unsigned short)(-1);
unsigned short n, arr[50000], iparent[50000][9], depth[50000], qna[50000],
    qnb[50000], nb, nbx, mk, mkb;
long q;
vector<unsigned short> edges[50000];
vector<pair<unsigned short, long>> queriea[50000];
vector<pair<unsigned short, long>> querieb[50000];
void dfs(unsigned short i, unsigned short p, unsigned short d) {
  iparent[i][0] = p, depth[i] = d;
  for (unsigned short l = 0; l + 1 < 9 && iparent[i][l] != NIL; l++)
    iparent[i][l + 1] = iparent[iparent[i][l]][l];
  for (unsigned short j = 0; j < edges[i].size(); j++)
    if (edges[i][j] != p) dfs(edges[i][j], i, d + 1);
}
unsigned short swap_bits(unsigned short x) {
  return ((x & nbx) << mkb) + (x >> mkb);
}
void search(long iq, unsigned short du, unsigned short v) {
  unsigned short st = 0;
  for (; depth[v] - du >= nb; st += nb, v = iparent[v][mkb])
    querieb[v].push_back(make_pair(st, iq));
  queriea[v].push_back(make_pair(swap_bits(depth[v] - du + st), iq));
}
void pre_search(unsigned short du, unsigned short v) {
  for (; depth[v] - du >= nb; qnb[v]++, v = iparent[v][mkb])
    ;
  qna[v]++;
}
struct TRIE {
  unsigned short *data, nr, *arx, k;
  long kl, ml;
  TRIE(unsigned short mk) {
    k = mk, ml = 1 << k;
    arx = (unsigned short *)malloc(nb * sizeof(unsigned short));
    kl = (1 << (k + 1)) - 1;
    data = (unsigned short *)malloc(kl * sizeof(unsigned short));
    memset(data, 0, kl * sizeof(unsigned short));
  }
  void init(unsigned short j) {
    for (unsigned short l = 0; l < nb && j != NIL; l++, j = iparent[j][0])
      arx[l] = arr[j] ^ l;
    nr = 0;
  }
  void end() {
    for (unsigned short rr = 0; rr < nr; rr++)
      for (long l = arx[rr]; l != kl && data[l] != 0; l = (l >> 1) ^ ml)
        data[l] = 0;
  }
  ~TRIE() {
    free(data);
    free(arx);
  }
  unsigned short query(unsigned short r, unsigned short high) {
    for (; nr < r; nr++)
      for (long l = arx[nr], p = l + 1; l != kl; l = (l >> 1) ^ ml)
        data[l] = max(data[l], (unsigned short)p);
    unsigned short ans = 0;
    for (long l = kl ^ 3, mask = ml >> 1; mask != 0; mask >>= 1) {
      unsigned short u = ((high & mask) == 0), x = (data[l ^ u] != 0);
      ans = (ans << 1) ^ x;
      if ((high & (mask - 1)) == 0)
        return ((data[l ^ u ^ x ^ 1] - 1) & (mask - 1)) + ans * mask;
      else
        l = ((l ^ u ^ x ^ 1) << 1) & kl;
    }
    return ans;
  }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  unsigned short u, v;
  long m;
  cin >> n >> q;
  for (unsigned short i = 0; i < n; i++) cin >> arr[i];
  for (unsigned short i = 0; i < n - 1; i++) {
    cin >> u >> v;
    u--, v--;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  memset(iparent, NIL, sizeof(iparent));
  dfs(0, NIL, 0);
  for (m = 1, mk = 0; m < n; m <<= 1, mk++)
    ;
  mkb = (mk & 1) ? 1 + (mk >> 1) : (mk >> 1);
  nb = 1 << mkb;
  nbx = nb - 1;
  if (m == n) mk++;
  unsigned short qans[q];
  memset(qans, 0, q * sizeof(unsigned short));
  unsigned short *qu = new unsigned short[q], *qv = new unsigned short[q];
  for (long i = 0; i < q; i++) {
    cin >> u >> v;
    pre_search(qu[i] = depth[u - 1], qv[i] = v - 1);
  }
  for (unsigned short i = 0; i < n; i++) {
    queriea[i].reserve(qna[i]);
    querieb[i].reserve(qnb[i]);
  }
  for (long i = 0; i < q; i++) search(i, qu[i], qv[i]);
  delete[] qu, delete[] qv;
  TRIE trie(mk);
  for (unsigned short i = 0; i < n; i++) {
    if (queriea[i].size() == 0 && querieb[i].size() == 0) continue;
    sort(queriea[i].begin(), queriea[i].end());
    trie.init(i);
    unsigned short imax = 0, pre = NIL, ipre;
    for (auto &jr : {queriea, querieb}) {
      pre = NIL;
      for (auto &j : jr[i]) {
        unsigned short &iaft = qans[j.second];
        ipre = j.first;
        if (pre != ipre) {
          pre = ipre;
          imax = jr == querieb
                     ? trie.query(nb, pre)
                     : trie.query((pre >> mkb) + 1, (pre & nbx) << mkb);
        }
        if (imax > iaft) iaft = imax;
      }
    }
    trie.end();
  }
  for (long i = 0; i < q; i++) cout << qans[i] << endl;
  return 0;
}

```