#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const long long LL_INF = 1ll * INF * INF;
const int MAX_N = 50000 + 7;
const int mod = 998244353;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
const int M = 16;
const int REV = 8;
const int MAGIC = 1 << REV;
struct Node {
  int left_index, right_index;
  int lhs_child, rhs_child;
  int mid_index = 0;
  void init(int left_index_, int right_index_, int lhs_child_, int rhs_child_) {
    left_index = left_index_;
    right_index = right_index_;
    lhs_child = lhs_child_;
    rhs_child = rhs_child_;
    mid_index = (left_index + right_index) >> 1;
  }
};
vector<Node> tree;
void build_node(Node& root, int left_index, int right_index) {
  if (left_index == right_index) {
    root.init(left_index, right_index, -1, -1);
    return;
  }
  int mid = (left_index + right_index) / 2;
  static int cnt = 1;
  int lhs = cnt++, rhs = cnt++;
  build_node(tree[lhs], left_index, mid);
  build_node(tree[rhs], mid + 1, right_index);
  root.init(left_index, right_index, lhs, rhs);
}
int trie_temp[MAGIC];
struct Trie {
  int max_value[2 * MAGIC];
  Trie() {}
  void build(int i) {
    if (tree[i].left_index == tree[i].right_index) {
      max_value[i] = trie_temp[tree[i].left_index];
      return;
    }
    build(tree[i].lhs_child);
    build(tree[i].rhs_child);
    max_value[i] =
        max(max_value[tree[i].lhs_child], max_value[tree[i].rhs_child]);
  }
  void update(int pos, int val) { update_max(trie_temp[pos], val); }
  int pre_calc[MAGIC];
};
void add_number(Trie& root, int a) { root.update(a >> REV, a & (MAGIC - 1)); }
int get_max(const Trie& root, const bitset<M>& a) {
  int root_index = 0;
  int res = 0;
  for (int j = REV - 1; j >= 0; --j) {
    bool c = a[j];
    int side[2] = {tree[root_index].lhs_child, tree[root_index].rhs_child};
    if (root.max_value[side[c ^ 1]] >= 0) {
      res |= 1 << j;
      root_index = side[c ^ 1];
    } else {
      if (root.max_value[side[c]] < 0) return -INF;
      root_index = side[c];
    }
  }
  return (res << REV) + root.max_value[root_index];
}
int n, q;
vector<int> adj[MAX_N];
int a[MAX_N];
int depth[MAX_N];
int parent[MAX_N];
Trie trie[MAX_N];
int nxt[MAX_N];
void dfs(int u, int r) {
  parent[u] = r;
  for (int v : adj[u])
    if (v != r) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
}
void solve() {
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(0, -1);
  tree.resize(MAGIC * 2);
  build_node(tree[0], 0, MAGIC - 1);
  for (int v = 0; v < n; ++v)
    if (depth[v] + 1 >= MAGIC) {
      int u = v;
      fill_n(trie_temp, MAGIC, -INF);
      for (int t = 0; t < MAGIC; ++t) {
        add_number(trie[v], a[u] ^ (depth[v] - depth[u]));
        u = parent[u];
      }
      trie[v].build(0);
      for (int t = 0; t < MAGIC; ++t) {
        trie[v].pre_calc[t] = get_max(trie[v], t);
      }
      nxt[v] = u;
    }
  int full = (1 << M) - 1;
  while (q-- > 0) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    int temp = v;
    int ans = 0;
    int t = 0;
    while (temp != -1 && depth[temp] - depth[u] + 1 >= MAGIC && ans < full) {
      ans = max(ans, trie[temp].pre_calc[t++]);
      temp = nxt[temp];
    }
    while (temp != -1 && temp != parent[u] && ans < full) {
      ans = max(ans, a[temp] ^ (depth[v] - depth[temp]));
      temp = parent[temp];
    }
    cout << ans << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

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 int INF = 1e9 + 7;
const long long LL_INF = 1ll * INF * INF;
const int MAX_N = 50000 + 7;
const int mod = 998244353;
template <typename num_t>
inline void addmod(num_t& a, const long long& b, const int& m) {
  a = (a + b) % m;
  if (a < 0) a += m;
}
template <typename num_t>
inline void update_max(num_t& a, const num_t& b) {
  a = max(a, b);
}
template <typename num_t>
inline void update_min(num_t& a, const num_t& b) {
  a = min(a, b);
}
const int M = 16;
const int REV = 8;
const int MAGIC = 1 << REV;
struct Node {
  int left_index, right_index;
  int lhs_child, rhs_child;
  int mid_index = 0;
  void init(int left_index_, int right_index_, int lhs_child_, int rhs_child_) {
    left_index = left_index_;
    right_index = right_index_;
    lhs_child = lhs_child_;
    rhs_child = rhs_child_;
    mid_index = (left_index + right_index) >> 1;
  }
};
vector<Node> tree;
void build_node(Node& root, int left_index, int right_index) {
  if (left_index == right_index) {
    root.init(left_index, right_index, -1, -1);
    return;
  }
  int mid = (left_index + right_index) / 2;
  static int cnt = 1;
  int lhs = cnt++, rhs = cnt++;
  build_node(tree[lhs], left_index, mid);
  build_node(tree[rhs], mid + 1, right_index);
  root.init(left_index, right_index, lhs, rhs);
}
int trie_temp[MAGIC];
struct Trie {
  int max_value[2 * MAGIC];
  Trie() {}
  void build(int i) {
    if (tree[i].left_index == tree[i].right_index) {
      max_value[i] = trie_temp[tree[i].left_index];
      return;
    }
    build(tree[i].lhs_child);
    build(tree[i].rhs_child);
    max_value[i] =
        max(max_value[tree[i].lhs_child], max_value[tree[i].rhs_child]);
  }
  void update(int pos, int val) { update_max(trie_temp[pos], val); }
  int pre_calc[MAGIC];
};
void add_number(Trie& root, int a) { root.update(a >> REV, a & (MAGIC - 1)); }
int get_max(const Trie& root, const bitset<M>& a) {
  int root_index = 0;
  int res = 0;
  for (int j = REV - 1; j >= 0; --j) {
    bool c = a[j];
    int side[2] = {tree[root_index].lhs_child, tree[root_index].rhs_child};
    if (root.max_value[side[c ^ 1]] >= 0) {
      res |= 1 << j;
      root_index = side[c ^ 1];
    } else {
      if (root.max_value[side[c]] < 0) return -INF;
      root_index = side[c];
    }
  }
  return (res << REV) + root.max_value[root_index];
}
int n, q;
vector<int> adj[MAX_N];
int a[MAX_N];
int depth[MAX_N];
int parent[MAX_N];
Trie trie[MAX_N];
int nxt[MAX_N];
void dfs(int u, int r) {
  parent[u] = r;
  for (int v : adj[u])
    if (v != r) {
      depth[v] = depth[u] + 1;
      dfs(v, u);
    }
}
void solve() {
  cin >> n >> q;
  for (int i = 0; i < n; ++i) cin >> a[i];
  for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(0, -1);
  tree.resize(MAGIC * 2);
  build_node(tree[0], 0, MAGIC - 1);
  for (int v = 0; v < n; ++v)
    if (depth[v] + 1 >= MAGIC) {
      int u = v;
      fill_n(trie_temp, MAGIC, -INF);
      for (int t = 0; t < MAGIC; ++t) {
        add_number(trie[v], a[u] ^ (depth[v] - depth[u]));
        u = parent[u];
      }
      trie[v].build(0);
      for (int t = 0; t < MAGIC; ++t) {
        trie[v].pre_calc[t] = get_max(trie[v], t);
      }
      nxt[v] = u;
    }
  int full = (1 << M) - 1;
  while (q-- > 0) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    int temp = v;
    int ans = 0;
    int t = 0;
    while (temp != -1 && depth[temp] - depth[u] + 1 >= MAGIC && ans < full) {
      ans = max(ans, trie[temp].pre_calc[t++]);
      temp = nxt[temp];
    }
    while (temp != -1 && temp != parent[u] && ans < full) {
      ans = max(ans, a[temp] ^ (depth[v] - depth[temp]));
      temp = parent[temp];
    }
    cout << ans << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  const bool multiple_test = false;
  int test = 1;
  if (multiple_test) cin >> test;
  for (int i = 0; i < test; ++i) {
    solve();
  }
}

```