#include <bits/stdc++.h>
using namespace std;
template <typename... As>
struct tpl : public std::tuple<As...> {
  using std::tuple<As...>::tuple;
  tpl(std::tuple<As...> const& b) { std::tuple<As...>::operator=(b); }
  template <typename T = tuple<As...>>
  typename tuple_element<0, T>::type const& x() const {
    return get<0>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<0, T>::type& x() {
    return get<0>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<1, T>::type const& y() const {
    return get<1>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<1, T>::type& y() {
    return get<1>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<2, T>::type const& z() const {
    return get<2>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<2, T>::type& z() {
    return get<2>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<3, T>::type const& w() const {
    return get<3>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<3, T>::type& w() {
    return get<3>(*this);
  }
};
using lli = long long int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_queue = priority_queue<T>;
template <size_t... I>
struct my_index_sequence {
  using type = my_index_sequence;
  static constexpr array<size_t, sizeof...(I)> value = {{I...}};
};
namespace my_index_sequence_detail {
template <typename I, typename J>
struct concat;
template <size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...>>
    : my_index_sequence<I..., (sizeof...(I) + J)...> {};
template <size_t N>
struct make_index_sequence
    : concat<typename make_index_sequence<N / 2>::type,
             typename make_index_sequence<N - N / 2>::type>::type {};
template <>
struct make_index_sequence<0> : my_index_sequence<> {};
template <>
struct make_index_sequence<1> : my_index_sequence<0> {};
}  // namespace my_index_sequence_detail
template <class... A>
using my_index_sequence_for =
    typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template <class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
}
template <class T>
ostream& print_collection(ostream& s, T const& a);
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template <class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, multiset<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
  s << '[';
  for (auto it = begin(a); it != end(a); ++it) {
    s << *it;
    if (it != prev(end(a))) s << " ";
  }
  return s << ']';
}
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
namespace std {
namespace {
template <class T>
inline void hash_combine(size_t& seed, T const& v) {
  seed ^= hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <class Tuple, size_t Index = tuple_size<Tuple>::value - 1>
struct HashValueImpl {
  static void apply(size_t& seed, Tuple const& tuple) {
    HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
    hash_combine(seed, get<Index>(tuple));
  }
};
template <class Tuple>
struct HashValueImpl<Tuple, 0> {
  static void apply(size_t& seed, Tuple const& tuple) {
    hash_combine(seed, get<0>(tuple));
  }
};
}  // namespace
template <typename... TT>
struct hash<tuple<TT...>> {
  size_t operator()(tuple<TT...> const& tt) const {
    size_t seed = 0;
    HashValueImpl<tuple<TT...>>::apply(seed, tt);
    return seed;
  }
};
template <typename... TT>
struct hash<tpl<TT...>> {
  size_t operator()(tpl<TT...> const& tt) const {
    size_t seed = 0;
    HashValueImpl<tuple<TT...>>::apply(seed, tt);
    return seed;
  }
};
}  // namespace std
const int N = 50000;
const int LN = 17;
const int M = 256;
const int LM = 8;
int parent[LN][N];
int depth[N];
int low[N][M], high[N][M];
bool trieCs[2048][2];
void clear(int i) {
  for (lli j = 0; j < (lli)(2); ++j)
    if (trieCs[i][j]) {
      trieCs[i][j] = 0;
      clear(2 * i + j);
    }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vi A(n);
  for (lli i = 0; i < (lli)(n); ++i) cin >> A[i];
  vvi G(n);
  for (lli i = 0; i < (lli)(n - 1); ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  function<void(int, int, int)> dfs = [&](int i, int p, int d) {
    parent[0][i] = p;
    depth[i] = d;
    for (int j : G[i])
      if (j != p) {
        dfs(j, i, d + 1);
      }
  };
  dfs(0, -1, 0);
  for (lli j = 0; j < (lli)(LN - 1); ++j) {
    for (lli i = 0; i < (lli)(n); ++i)
      if (parent[j][i] == -1) {
        parent[j + 1][i] = -1;
      } else {
        parent[j + 1][i] = parent[j][parent[j][i]];
      }
  }
  for (lli i = 0; i < (lli)(n); ++i)
    if (parent[LM][i] != -1) {
      int v = i;
      for (lli j = 0; j < (lli)(M); ++j) {
        low[i][A[v] >> 8] = max<int>(low[i][A[v] >> 8], (A[v] & 255) ^ j);
        {
          int p = 1;
          for (lli k = 0; k < (lli)(8); ++k)
            if (A[v] & (1 << (15 - k))) {
              trieCs[p][1] = 1;
              p = 2 * p + 1;
            } else {
              trieCs[p][0] = 1;
              p = 2 * p;
            };
        }
        v = parent[0][v];
      }
      for (lli j = 0; j < (lli)(M); ++j) {
        int p = 1;
        high[i][j] = 0;
        for (lli k = 0; k < (lli)(8); ++k) {
          if (j & (1 << (7 - k))) {
            if (trieCs[p][0]) {
              p = 2 * p;
              high[i][j] += (1 << (7 - k));
            } else {
              p = 2 * p + 1;
            }
          } else {
            if (trieCs[p][1]) {
              p = 2 * p + 1;
              high[i][j] += (1 << (7 - k));
            } else
              p = 2 * p;
          }
        }
      }
      clear(1);
    }
  for (lli q_ = 0; q_ < (lli)(q); ++q_) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    int i = v;
    int best = 0;
    int j = 0;
    while (parent[LM][i] != -1 && depth[parent[LM][i]] >= depth[u]) {
      int hi = high[i][j];
      int lo = low[i][hi ^ j];
      int cur = (hi << 8) + lo;
      best = max(best, cur);
      i = parent[LM][i];
      j += 1;
    }
    while (depth[i] > depth[u]) {
      if ((A[i] ^ (depth[v] - depth[i])) > best) {
        best = max<int>(best, A[i] ^ (depth[v] - depth[i]));
      }
      i = parent[0][i];
    }
    best = max<int>(best, A[i] ^ (depth[v] - depth[i]));
    printf("%d\n", best);
  }
  fflush(stdout);
  return 0;
}

### Prompt

Generate 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;
template <typename... As>
struct tpl : public std::tuple<As...> {
  using std::tuple<As...>::tuple;
  tpl(std::tuple<As...> const& b) { std::tuple<As...>::operator=(b); }
  template <typename T = tuple<As...>>
  typename tuple_element<0, T>::type const& x() const {
    return get<0>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<0, T>::type& x() {
    return get<0>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<1, T>::type const& y() const {
    return get<1>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<1, T>::type& y() {
    return get<1>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<2, T>::type const& z() const {
    return get<2>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<2, T>::type& z() {
    return get<2>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<3, T>::type const& w() const {
    return get<3>(*this);
  }
  template <typename T = tuple<As...>>
  typename tuple_element<3, T>::type& w() {
    return get<3>(*this);
  }
};
using lli = long long int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using max_queue = priority_queue<T>;
template <size_t... I>
struct my_index_sequence {
  using type = my_index_sequence;
  static constexpr array<size_t, sizeof...(I)> value = {{I...}};
};
namespace my_index_sequence_detail {
template <typename I, typename J>
struct concat;
template <size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...>>
    : my_index_sequence<I..., (sizeof...(I) + J)...> {};
template <size_t N>
struct make_index_sequence
    : concat<typename make_index_sequence<N / 2>::type,
             typename make_index_sequence<N - N / 2>::type>::type {};
template <>
struct make_index_sequence<0> : my_index_sequence<> {};
template <>
struct make_index_sequence<1> : my_index_sequence<0> {};
}  // namespace my_index_sequence_detail
template <class... A>
using my_index_sequence_for =
    typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template <class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
}
template <class T>
ostream& print_collection(ostream& s, T const& a);
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template <class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, multiset<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
  s << '[';
  for (auto it = begin(a); it != end(a); ++it) {
    s << *it;
    if (it != prev(end(a))) s << " ";
  }
  return s << ']';
}
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
namespace std {
namespace {
template <class T>
inline void hash_combine(size_t& seed, T const& v) {
  seed ^= hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template <class Tuple, size_t Index = tuple_size<Tuple>::value - 1>
struct HashValueImpl {
  static void apply(size_t& seed, Tuple const& tuple) {
    HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
    hash_combine(seed, get<Index>(tuple));
  }
};
template <class Tuple>
struct HashValueImpl<Tuple, 0> {
  static void apply(size_t& seed, Tuple const& tuple) {
    hash_combine(seed, get<0>(tuple));
  }
};
}  // namespace
template <typename... TT>
struct hash<tuple<TT...>> {
  size_t operator()(tuple<TT...> const& tt) const {
    size_t seed = 0;
    HashValueImpl<tuple<TT...>>::apply(seed, tt);
    return seed;
  }
};
template <typename... TT>
struct hash<tpl<TT...>> {
  size_t operator()(tpl<TT...> const& tt) const {
    size_t seed = 0;
    HashValueImpl<tuple<TT...>>::apply(seed, tt);
    return seed;
  }
};
}  // namespace std
const int N = 50000;
const int LN = 17;
const int M = 256;
const int LM = 8;
int parent[LN][N];
int depth[N];
int low[N][M], high[N][M];
bool trieCs[2048][2];
void clear(int i) {
  for (lli j = 0; j < (lli)(2); ++j)
    if (trieCs[i][j]) {
      trieCs[i][j] = 0;
      clear(2 * i + j);
    }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vi A(n);
  for (lli i = 0; i < (lli)(n); ++i) cin >> A[i];
  vvi G(n);
  for (lli i = 0; i < (lli)(n - 1); ++i) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  function<void(int, int, int)> dfs = [&](int i, int p, int d) {
    parent[0][i] = p;
    depth[i] = d;
    for (int j : G[i])
      if (j != p) {
        dfs(j, i, d + 1);
      }
  };
  dfs(0, -1, 0);
  for (lli j = 0; j < (lli)(LN - 1); ++j) {
    for (lli i = 0; i < (lli)(n); ++i)
      if (parent[j][i] == -1) {
        parent[j + 1][i] = -1;
      } else {
        parent[j + 1][i] = parent[j][parent[j][i]];
      }
  }
  for (lli i = 0; i < (lli)(n); ++i)
    if (parent[LM][i] != -1) {
      int v = i;
      for (lli j = 0; j < (lli)(M); ++j) {
        low[i][A[v] >> 8] = max<int>(low[i][A[v] >> 8], (A[v] & 255) ^ j);
        {
          int p = 1;
          for (lli k = 0; k < (lli)(8); ++k)
            if (A[v] & (1 << (15 - k))) {
              trieCs[p][1] = 1;
              p = 2 * p + 1;
            } else {
              trieCs[p][0] = 1;
              p = 2 * p;
            };
        }
        v = parent[0][v];
      }
      for (lli j = 0; j < (lli)(M); ++j) {
        int p = 1;
        high[i][j] = 0;
        for (lli k = 0; k < (lli)(8); ++k) {
          if (j & (1 << (7 - k))) {
            if (trieCs[p][0]) {
              p = 2 * p;
              high[i][j] += (1 << (7 - k));
            } else {
              p = 2 * p + 1;
            }
          } else {
            if (trieCs[p][1]) {
              p = 2 * p + 1;
              high[i][j] += (1 << (7 - k));
            } else
              p = 2 * p;
          }
        }
      }
      clear(1);
    }
  for (lli q_ = 0; q_ < (lli)(q); ++q_) {
    int u, v;
    cin >> u >> v;
    --u;
    --v;
    int i = v;
    int best = 0;
    int j = 0;
    while (parent[LM][i] != -1 && depth[parent[LM][i]] >= depth[u]) {
      int hi = high[i][j];
      int lo = low[i][hi ^ j];
      int cur = (hi << 8) + lo;
      best = max(best, cur);
      i = parent[LM][i];
      j += 1;
    }
    while (depth[i] > depth[u]) {
      if ((A[i] ^ (depth[v] - depth[i])) > best) {
        best = max<int>(best, A[i] ^ (depth[v] - depth[i]));
      }
      i = parent[0][i];
    }
    best = max<int>(best, A[i] ^ (depth[v] - depth[i]));
    printf("%d\n", best);
  }
  fflush(stdout);
  return 0;
}

```