#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MAXN = 5e4 + 5;
int n, q, a[MAXN];
int up[MAXN][20];
int dep[MAXN];
vector<int> path[MAXN];
int tin[MAXN], tout[MAXN];
void dfs(int u, int pre = 0) {
  static int timer = 0;
  tin[u] = ++timer;
  dep[u] = dep[pre] + 1;
  up[u][0] = pre;
  for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (int v : path[u])
    if (v != pre) dfs(v, u);
  tout[u] = timer;
}
bool anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v) {
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;
  for (int i = 19; i >= 0; i--)
    if (!anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}
struct node {
  node* child[2];
};
const int MAX_BUF = 10000;
node buffer[MAX_BUF];
int BUF_PTR = 0;
node* get_buf_node() {
  assert(BUF_PTR < MAX_BUF);
  return &buffer[BUF_PTR++];
}
node* new_node() {
  node* v = get_buf_node();
  v->child[0] = v->child[1] = nullptr;
  return v;
}
struct trie {
  node* root;
  trie() { root = new_node(); }
  void add(int v) {
    node* cur = root;
    for (int i = 20; i >= 0; i--) {
      if (cur->child[v >> i & 1] == nullptr)
        cur->child[v >> i & 1] = new_node();
      cur = cur->child[v >> i & 1];
    }
  }
  int query(int v) {
    node* cur = root;
    int val = 0;
    for (int i = 20; i >= 0; i--) {
      bool p = (v >> i & 1);
      if (cur->child[!p] != nullptr) p = !p;
      cur = cur->child[p];
      if (p) val |= (1 << i);
    }
    return val ^ v;
  }
};
int prec[MAXN][221];
int BITS = 8;
void prep() {
  for (int u = 1; u <= n; u++) {
    int cur = u;
    BUF_PTR = 0;
    trie v;
    for (int i = 0; i < (1 << BITS); i++) {
      if (!cur) break;
      v.add(a[cur] ^ i);
      cur = up[cur][0];
    }
    for (int d = 0; d <= 220; d++) prec[u][d] = v.query(d << BITS);
  }
}
void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    path[u].push_back(v);
    path[v].push_back(u);
  }
  tout[0] = 1e9;
  dfs(1);
  prep();
  while (q--) {
    int u, v;
    cin >> u >> v;
    int l = lca(u, v);
    int mx = 0;
    int cnt = 0;
    int vv = v, uu = u;
    while (abs(dep[v] - dep[l]) >= (1 << BITS) - 1) {
      mx = max(mx, prec[v][cnt]);
      cnt++;
      v = up[v][BITS];
    }
    int cc = 0;
    while (dep[v] >= dep[l]) {
      mx = max(mx, a[v] ^ (dep[vv] - dep[v]));
      v = up[v][0];
      cc++;
    }
    if (dep[u] - dep[l] <= 300) {
      while (dep[u] >= dep[l]) {
        mx = max(mx, a[u] ^ (dep[u] + dep[vv] - (dep[l] << 1)));
        u = up[u][0];
      }
      cout << mx << '\n';
      continue;
    }
    int rem = (1 << BITS) - cc;
    int ndep = dep[l] - rem + 1;
    int vdep;
    while (ndep < dep[u]) ndep += (1 << BITS);
    ndep -= (1 << BITS);
    while (dep[u] > ndep) {
      u = up[u][0];
      mx = max(mx, a[u] ^ (dep[u] + dep[vv] - (dep[l] << 1)));
    }
    while (abs(dep[u] - dep[l]) >= (1 << BITS) - 1) {
      int d = (dep[u] + dep[vv] - (dep[l] << 1) + 1) >> BITS - 1;
      mx = max(mx, prec[u][d]);
    }
    while (dep[u] >= dep[l]) {
      mx = max(mx, a[u] ^ (dep[vv] + dep[u] - (dep[l] << 1)));
      u = up[u][0];
    }
    cout << mx << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) solve();
}

### Prompt

Construct a CPP code solution to the problem outlined:

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>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
const int MAXN = 5e4 + 5;
int n, q, a[MAXN];
int up[MAXN][20];
int dep[MAXN];
vector<int> path[MAXN];
int tin[MAXN], tout[MAXN];
void dfs(int u, int pre = 0) {
  static int timer = 0;
  tin[u] = ++timer;
  dep[u] = dep[pre] + 1;
  up[u][0] = pre;
  for (int i = 1; i < 20; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (int v : path[u])
    if (v != pre) dfs(v, u);
  tout[u] = timer;
}
bool anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v) {
  if (anc(u, v)) return u;
  if (anc(v, u)) return v;
  for (int i = 19; i >= 0; i--)
    if (!anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}
struct node {
  node* child[2];
};
const int MAX_BUF = 10000;
node buffer[MAX_BUF];
int BUF_PTR = 0;
node* get_buf_node() {
  assert(BUF_PTR < MAX_BUF);
  return &buffer[BUF_PTR++];
}
node* new_node() {
  node* v = get_buf_node();
  v->child[0] = v->child[1] = nullptr;
  return v;
}
struct trie {
  node* root;
  trie() { root = new_node(); }
  void add(int v) {
    node* cur = root;
    for (int i = 20; i >= 0; i--) {
      if (cur->child[v >> i & 1] == nullptr)
        cur->child[v >> i & 1] = new_node();
      cur = cur->child[v >> i & 1];
    }
  }
  int query(int v) {
    node* cur = root;
    int val = 0;
    for (int i = 20; i >= 0; i--) {
      bool p = (v >> i & 1);
      if (cur->child[!p] != nullptr) p = !p;
      cur = cur->child[p];
      if (p) val |= (1 << i);
    }
    return val ^ v;
  }
};
int prec[MAXN][221];
int BITS = 8;
void prep() {
  for (int u = 1; u <= n; u++) {
    int cur = u;
    BUF_PTR = 0;
    trie v;
    for (int i = 0; i < (1 << BITS); i++) {
      if (!cur) break;
      v.add(a[cur] ^ i);
      cur = up[cur][0];
    }
    for (int d = 0; d <= 220; d++) prec[u][d] = v.query(d << BITS);
  }
}
void solve() {
  cin >> n >> q;
  for (int i = 1; i <= n; i++) cin >> a[i];
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    path[u].push_back(v);
    path[v].push_back(u);
  }
  tout[0] = 1e9;
  dfs(1);
  prep();
  while (q--) {
    int u, v;
    cin >> u >> v;
    int l = lca(u, v);
    int mx = 0;
    int cnt = 0;
    int vv = v, uu = u;
    while (abs(dep[v] - dep[l]) >= (1 << BITS) - 1) {
      mx = max(mx, prec[v][cnt]);
      cnt++;
      v = up[v][BITS];
    }
    int cc = 0;
    while (dep[v] >= dep[l]) {
      mx = max(mx, a[v] ^ (dep[vv] - dep[v]));
      v = up[v][0];
      cc++;
    }
    if (dep[u] - dep[l] <= 300) {
      while (dep[u] >= dep[l]) {
        mx = max(mx, a[u] ^ (dep[u] + dep[vv] - (dep[l] << 1)));
        u = up[u][0];
      }
      cout << mx << '\n';
      continue;
    }
    int rem = (1 << BITS) - cc;
    int ndep = dep[l] - rem + 1;
    int vdep;
    while (ndep < dep[u]) ndep += (1 << BITS);
    ndep -= (1 << BITS);
    while (dep[u] > ndep) {
      u = up[u][0];
      mx = max(mx, a[u] ^ (dep[u] + dep[vv] - (dep[l] << 1)));
    }
    while (abs(dep[u] - dep[l]) >= (1 << BITS) - 1) {
      int d = (dep[u] + dep[vv] - (dep[l] << 1) + 1) >> BITS - 1;
      mx = max(mx, prec[u][d]);
    }
    while (dep[u] >= dep[l]) {
      mx = max(mx, a[u] ^ (dep[vv] + dep[u] - (dep[l] << 1)));
      u = up[u][0];
    }
    cout << mx << '\n';
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) solve();
}

```