#include <bits/stdc++.h>
#pragma GCC optimize(2, 3, "Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const double pi = 3.141592653589793238462643383279;
namespace MyMinMax {
template <typename T>
inline T mn(const T x, const T y) {
  return x < y ? x : y;
}
template <typename T>
inline T mx(const T x, const T y) {
  return x > y ? x : y;
}
template <typename T>
inline bool chmin(T &x, const T y) {
  return (x > y) && ((x = y), 1);
}
template <typename T>
inline bool chmax(T &x, const T y) {
  return (x < y) && ((x = y), 1);
}
template <typename T, typename... Args>
inline T mx(const T x, const Args... args) {
  return mx(x, mx(args...));
}
template <typename T, typename... Args>
inline T mn(const T x, const Args... args) {
  return mn(x, mn(args...));
}
}  // namespace MyMinMax
using namespace MyMinMax;
namespace IO {
const int DPAIRSIZ = 1 << 18;
char BB[DPAIRSIZ], *SS = BB, *TT = BB;
inline char getcha() {
  return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT)
             ? EOF
             : *SS++;
}
template <typename T = int>
inline T read() {
  T x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
  return x;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
}
template <typename T>
inline void read(T *bg, T *ed) {
  while (bg != ed) read(*bg++);
}
inline void read(char &ch) {
  ch = getcha();
  while (ch <= 32) ch = getcha();
}
inline void read(char *s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void sread(char *s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void pread(char *&s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void spread(char *&s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
char out[DPAIRSIZ], *Out = out;
inline void putcha(char x) {
  *Out++ = x;
  if (Out - out >= (DPAIRSIZ)) fwrite(out, 1, Out - out, stdout), Out = out;
}
template <typename T>
inline void fprint(T x) {
  if (x < 0) putcha(45), x = -x;
  if (x > 9) fprint(x / 10);
  putcha(x % 10 + 48);
}
inline void print() { putcha(10); }
template <typename T>
inline void print(T x) {
  fprint(x);
  putcha(10);
}
inline void print(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
inline void print(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
template <typename T, typename... Args>
inline void print(T x, Args... args) {
  fprint(x);
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename T, typename... Args>
inline void printl(T x, Args... args) {
  fprint(x);
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename T>
inline void sprint(T x) {
  fprint(x);
  putcha(32);
}
template <typename T, typename... Args>
inline void sprint(T x, Args... args) {
  fprint(x);
  putcha(32);
  sprint(args...);
}
template <typename T>
inline void sprint(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
}
template <typename T>
inline void print(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
  putcha(10);
}
template <typename T>
inline void printl(T *bg, T *ed) {
  while (bg != ed) print(*bg++);
}
class AutoFlush {
 public:
  ~AutoFlush() { fwrite(out, 1, Out - out, stdout); }
} __AutoFlush;
}  // namespace IO
using namespace IO;
const int INF = 0x3f3f3f3f;
const long long INFll = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 5e4 + 5;
int n, q, a[MAXN];
int head[MAXN], e[MAXN << 1], cnt, nxt[MAXN << 1];
inline void add(int u, int v) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  e[cnt] = v;
}
inline void link(int u, int v) {
  add(u, v);
  add(v, u);
}
int Trie[MAXN][2], tot;
inline void clear() { tot = Trie[0][0] = Trie[0][1] = 0; }
inline int NewNode() {
  const int rt = ++tot;
  Trie[rt][0] = Trie[rt][1] = 0;
  return rt;
}
inline void ins(const int x) {
  int rt = 0;
  for (int i = (7); i >= (0); --i) {
    const bool ck = x >> i & 1;
    if (!Trie[rt][ck]) Trie[rt][ck] = NewNode();
    rt = Trie[rt][ck];
  }
}
int g[256];
inline int query(const int x) {
  int rt = 0, ret = 0;
  for (int i = (7); i >= (0); --i) {
    const int ck = x >> i & 1;
    if (Trie[rt][ck ^ 1])
      ret |= ((ck ^ 1) << i), rt = Trie[rt][ck ^ 1];
    else
      ret |= (ck << i), rt = Trie[rt][ck];
  }
  return ((ret ^ x) << 8) | g[ret];
}
int fa[MAXN], f[MAXN][256], p[MAXN], dep[MAXN];
int t[256];
const int lim = 256;
void dfs(int x, int pre) {
  dep[x] = dep[fa[x] = pre] + 1;
  if (dep[x] >= lim) {
    memset(g, 0, sizeof(g));
    clear();
    int u = x;
    while (dep[x] - dep[u] < lim) {
      const int v = a[u] >> 8;
      chmax(g[v], (a[u] ^ (dep[x] - dep[u])) & 255);
      if (t[v] != x) ins(v), t[v] = x;
      u = fa[u];
    }
    for (int i = (0); i < (lim); ++i) f[x][i] = query(i);
    p[x] = u;
  }
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dfs(e[i], x);
  }
}
signed main() {
  read(n, q);
  read(a + 1, a + n + 1);
  for (int i = (2); i <= (n); ++i) link(read(), read());
  dfs(1, 0);
  while (q--) {
    int u, v;
    read(u, v);
    int d = 0, ans = 0;
    while (dep[v] - dep[u] >= lim) {
      chmax(ans, f[v][d]);
      v = p[v];
      ++d;
    }
    d <<= 8;
    while (v ^ fa[u]) {
      chmax(ans, a[v] ^ d);
      v = fa[v];
      ++d;
    }
    print(ans);
  }
}

### Prompt

Develop a solution in cpp 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>
#pragma GCC optimize(2, 3, "Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const double pi = 3.141592653589793238462643383279;
namespace MyMinMax {
template <typename T>
inline T mn(const T x, const T y) {
  return x < y ? x : y;
}
template <typename T>
inline T mx(const T x, const T y) {
  return x > y ? x : y;
}
template <typename T>
inline bool chmin(T &x, const T y) {
  return (x > y) && ((x = y), 1);
}
template <typename T>
inline bool chmax(T &x, const T y) {
  return (x < y) && ((x = y), 1);
}
template <typename T, typename... Args>
inline T mx(const T x, const Args... args) {
  return mx(x, mx(args...));
}
template <typename T, typename... Args>
inline T mn(const T x, const Args... args) {
  return mn(x, mn(args...));
}
}  // namespace MyMinMax
using namespace MyMinMax;
namespace IO {
const int DPAIRSIZ = 1 << 18;
char BB[DPAIRSIZ], *SS = BB, *TT = BB;
inline char getcha() {
  return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT)
             ? EOF
             : *SS++;
}
template <typename T = int>
inline T read() {
  T x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
  return x;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int fu = 1;
  char c = getcha();
  while (c > 57 || c < 48) {
    if (c == 45) fu = -1;
    c = getcha();
  }
  while (c <= 57 && c >= 48) {
    x = x * 10 + c - 48;
    c = getcha();
  }
  x *= fu;
}
template <typename T>
inline void read(T *bg, T *ed) {
  while (bg != ed) read(*bg++);
}
inline void read(char &ch) {
  ch = getcha();
  while (ch <= 32) ch = getcha();
}
inline void read(char *s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void sread(char *s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void pread(char *&s) {
  char ch = getcha();
  while (ch <= 32) ch = getcha();
  while (ch > 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
inline void spread(char *&s) {
  char ch = getcha();
  while (ch < 32) ch = getcha();
  while (ch >= 32) *s++ = ch, ch = getcha();
  *s = '\0';
}
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
char out[DPAIRSIZ], *Out = out;
inline void putcha(char x) {
  *Out++ = x;
  if (Out - out >= (DPAIRSIZ)) fwrite(out, 1, Out - out, stdout), Out = out;
}
template <typename T>
inline void fprint(T x) {
  if (x < 0) putcha(45), x = -x;
  if (x > 9) fprint(x / 10);
  putcha(x % 10 + 48);
}
inline void print() { putcha(10); }
template <typename T>
inline void print(T x) {
  fprint(x);
  putcha(10);
}
inline void print(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
inline void print(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
}
inline void put(const char *ch) {
  while (*ch != '\0') putcha(*(ch++));
}
template <typename T, typename... Args>
inline void print(T x, Args... args) {
  fprint(x);
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename... Args>
inline void print(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(32);
  print(args...);
}
template <typename T, typename... Args>
inline void printl(T x, Args... args) {
  fprint(x);
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(const char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename... Args>
inline void printl(char *ch, Args... args) {
  while (*ch != '\0') putcha(*(ch++));
  putcha(10);
  printl(args...);
}
template <typename T>
inline void sprint(T x) {
  fprint(x);
  putcha(32);
}
template <typename T, typename... Args>
inline void sprint(T x, Args... args) {
  fprint(x);
  putcha(32);
  sprint(args...);
}
template <typename T>
inline void sprint(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
}
template <typename T>
inline void print(T *bg, T *ed) {
  while (bg != ed) sprint(*bg++);
  putcha(10);
}
template <typename T>
inline void printl(T *bg, T *ed) {
  while (bg != ed) print(*bg++);
}
class AutoFlush {
 public:
  ~AutoFlush() { fwrite(out, 1, Out - out, stdout); }
} __AutoFlush;
}  // namespace IO
using namespace IO;
const int INF = 0x3f3f3f3f;
const long long INFll = 0x3f3f3f3f3f3f3f3fll;
const int MAXN = 5e4 + 5;
int n, q, a[MAXN];
int head[MAXN], e[MAXN << 1], cnt, nxt[MAXN << 1];
inline void add(int u, int v) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  e[cnt] = v;
}
inline void link(int u, int v) {
  add(u, v);
  add(v, u);
}
int Trie[MAXN][2], tot;
inline void clear() { tot = Trie[0][0] = Trie[0][1] = 0; }
inline int NewNode() {
  const int rt = ++tot;
  Trie[rt][0] = Trie[rt][1] = 0;
  return rt;
}
inline void ins(const int x) {
  int rt = 0;
  for (int i = (7); i >= (0); --i) {
    const bool ck = x >> i & 1;
    if (!Trie[rt][ck]) Trie[rt][ck] = NewNode();
    rt = Trie[rt][ck];
  }
}
int g[256];
inline int query(const int x) {
  int rt = 0, ret = 0;
  for (int i = (7); i >= (0); --i) {
    const int ck = x >> i & 1;
    if (Trie[rt][ck ^ 1])
      ret |= ((ck ^ 1) << i), rt = Trie[rt][ck ^ 1];
    else
      ret |= (ck << i), rt = Trie[rt][ck];
  }
  return ((ret ^ x) << 8) | g[ret];
}
int fa[MAXN], f[MAXN][256], p[MAXN], dep[MAXN];
int t[256];
const int lim = 256;
void dfs(int x, int pre) {
  dep[x] = dep[fa[x] = pre] + 1;
  if (dep[x] >= lim) {
    memset(g, 0, sizeof(g));
    clear();
    int u = x;
    while (dep[x] - dep[u] < lim) {
      const int v = a[u] >> 8;
      chmax(g[v], (a[u] ^ (dep[x] - dep[u])) & 255);
      if (t[v] != x) ins(v), t[v] = x;
      u = fa[u];
    }
    for (int i = (0); i < (lim); ++i) f[x][i] = query(i);
    p[x] = u;
  }
  for (int i = head[x]; i; i = nxt[i]) {
    if (e[i] == pre) continue;
    dfs(e[i], x);
  }
}
signed main() {
  read(n, q);
  read(a + 1, a + n + 1);
  for (int i = (2); i <= (n); ++i) link(read(), read());
  dfs(1, 0);
  while (q--) {
    int u, v;
    read(u, v);
    int d = 0, ans = 0;
    while (dep[v] - dep[u] >= lim) {
      chmax(ans, f[v][d]);
      v = p[v];
      ++d;
    }
    d <<= 8;
    while (v ^ fa[u]) {
      chmax(ans, a[v] ^ d);
      v = fa[v];
      ++d;
    }
    print(ans);
  }
}

```