#include <bits/stdc++.h>
using namespace std;
inline int Read() {
  int x(0), f(1);
  char c(getchar());
  while (c < '0' || '9' < c) {
    if (c == '-') {
      f = -1;
    }
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return f * x;
}
void Write(int x) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (9 < x) {
    Write(x / 10);
  }
  putchar(x % 10 + '0');
}
inline void Writeln(int x) {
  Write(x);
  puts("");
}
const int MAXN = 1e5 + 5;
const int MAXM = MAXN << 1;
int n, m, root;
int val[MAXN];
const int log_num = 7;
struct Trie {
  int son[2];
} trie[MAXN * 32];
int trie_cnt = 0;
int trie_tot = 0;
int rubbish[MAXN * 32];
int NewTrie() {
  if (trie_tot) {
    return rubbish[trie_tot--];
  }
  return ++trie_cnt;
}
void Delete(int &now) {
  trie[now].son[0] = trie[now].son[1] = 0;
  rubbish[++trie_tot] = now;
  now = 0;
}
void Clean(int &now) {
  if (!now) {
    return;
  }
  Clean(trie[now].son[0]);
  Clean(trie[now].son[1]);
  Delete(now);
}
void Insert(int num, int &now, int deep = log_num) {
  if (!now) {
    now = NewTrie();
  }
  if (~deep) {
    bool p = num & (1 << deep);
    Insert(num, trie[now].son[p], deep - 1);
  }
}
int max_len[MAXN][257];
int Query(int num, int q, int &now, int deep = log_num, int result = 0,
          int max_num = 0) {
  if (~deep) {
    bool p = num & (1 << deep);
    if (trie[now].son[p ^ 1]) {
      return Query(num, q, trie[now].son[p ^ 1], deep - 1,
                   (p ^ 1) << deep | result, 1 << deep | max_num);
    } else {
      return Query(num, q, trie[now].son[p], deep - 1, p << deep | result,
                   max_num);
    }
  } else {
    return max_num << 8 | max_len[q][result];
  }
}
struct Edge {
  int to, next;
} edge[MAXM];
int edge_head[MAXN];
int edge_cnt = 0;
void AddEdge(int form, int to) {
  edge[++edge_cnt].to = to;
  edge[edge_cnt].next = edge_head[form];
  edge_head[form] = edge_cnt;
}
int f[MAXN][257];
int father[MAXN];
int deep[MAXN] = {0, 1};
int top[MAXN];
int visit[257];
void DFS(int now = 1) {
  if (256 <= deep[now]) {
    Clean(root);
    int fa = now;
    while (deep[now] - deep[fa] < 256) {
      max_len[now][val[fa] >> 8] = max(max_len[now][val[fa] >> 8],
                                       (deep[now] - deep[fa] ^ val[fa]) & 255);
      if (visit[val[fa] >> 8] ^ now) {
        visit[val[fa] >> 8] = now;
        Insert(val[fa] >> 8, root);
      }
      fa = father[fa];
    }
    top[now] = fa;
    for (int i = 0; i <= 255; ++i) {
      f[now][i] = Query(i, now, root);
    }
  }
  for (int edge_i = edge_head[now]; edge_i; edge_i = edge[edge_i].next) {
    if (edge[edge_i].to ^ father[now]) {
      father[edge[edge_i].to] = now;
      deep[edge[edge_i].to] = deep[now] + 1;
      DFS(edge[edge_i].to);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &val[i]);
  }
  int a, b;
  for (int i = 1; i <= n - 1; ++i) {
    a = Read();
    b = Read();
    AddEdge(a, b);
    AddEdge(b, a);
  }
  DFS();
  for (int i = 1; i <= m; ++i) {
    a = Read();
    b = Read();
    int answer = 0, dis = 0;
    while (256 <= deep[b] - deep[a]) {
      answer = max(answer, f[b][dis]);
      b = top[b];
      ++dis;
    }
    dis <<= 8;
    while (b ^ father[a]) {
      answer = max(answer, val[b] ^ dis);
      b = father[b];
      dis++;
    }
    printf("%d\n", answer);
  }
  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;
inline int Read() {
  int x(0), f(1);
  char c(getchar());
  while (c < '0' || '9' < c) {
    if (c == '-') {
      f = -1;
    }
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = (x << 1) + (x << 3) + c - '0';
    c = getchar();
  }
  return f * x;
}
void Write(int x) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (9 < x) {
    Write(x / 10);
  }
  putchar(x % 10 + '0');
}
inline void Writeln(int x) {
  Write(x);
  puts("");
}
const int MAXN = 1e5 + 5;
const int MAXM = MAXN << 1;
int n, m, root;
int val[MAXN];
const int log_num = 7;
struct Trie {
  int son[2];
} trie[MAXN * 32];
int trie_cnt = 0;
int trie_tot = 0;
int rubbish[MAXN * 32];
int NewTrie() {
  if (trie_tot) {
    return rubbish[trie_tot--];
  }
  return ++trie_cnt;
}
void Delete(int &now) {
  trie[now].son[0] = trie[now].son[1] = 0;
  rubbish[++trie_tot] = now;
  now = 0;
}
void Clean(int &now) {
  if (!now) {
    return;
  }
  Clean(trie[now].son[0]);
  Clean(trie[now].son[1]);
  Delete(now);
}
void Insert(int num, int &now, int deep = log_num) {
  if (!now) {
    now = NewTrie();
  }
  if (~deep) {
    bool p = num & (1 << deep);
    Insert(num, trie[now].son[p], deep - 1);
  }
}
int max_len[MAXN][257];
int Query(int num, int q, int &now, int deep = log_num, int result = 0,
          int max_num = 0) {
  if (~deep) {
    bool p = num & (1 << deep);
    if (trie[now].son[p ^ 1]) {
      return Query(num, q, trie[now].son[p ^ 1], deep - 1,
                   (p ^ 1) << deep | result, 1 << deep | max_num);
    } else {
      return Query(num, q, trie[now].son[p], deep - 1, p << deep | result,
                   max_num);
    }
  } else {
    return max_num << 8 | max_len[q][result];
  }
}
struct Edge {
  int to, next;
} edge[MAXM];
int edge_head[MAXN];
int edge_cnt = 0;
void AddEdge(int form, int to) {
  edge[++edge_cnt].to = to;
  edge[edge_cnt].next = edge_head[form];
  edge_head[form] = edge_cnt;
}
int f[MAXN][257];
int father[MAXN];
int deep[MAXN] = {0, 1};
int top[MAXN];
int visit[257];
void DFS(int now = 1) {
  if (256 <= deep[now]) {
    Clean(root);
    int fa = now;
    while (deep[now] - deep[fa] < 256) {
      max_len[now][val[fa] >> 8] = max(max_len[now][val[fa] >> 8],
                                       (deep[now] - deep[fa] ^ val[fa]) & 255);
      if (visit[val[fa] >> 8] ^ now) {
        visit[val[fa] >> 8] = now;
        Insert(val[fa] >> 8, root);
      }
      fa = father[fa];
    }
    top[now] = fa;
    for (int i = 0; i <= 255; ++i) {
      f[now][i] = Query(i, now, root);
    }
  }
  for (int edge_i = edge_head[now]; edge_i; edge_i = edge[edge_i].next) {
    if (edge[edge_i].to ^ father[now]) {
      father[edge[edge_i].to] = now;
      deep[edge[edge_i].to] = deep[now] + 1;
      DFS(edge[edge_i].to);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &val[i]);
  }
  int a, b;
  for (int i = 1; i <= n - 1; ++i) {
    a = Read();
    b = Read();
    AddEdge(a, b);
    AddEdge(b, a);
  }
  DFS();
  for (int i = 1; i <= m; ++i) {
    a = Read();
    b = Read();
    int answer = 0, dis = 0;
    while (256 <= deep[b] - deep[a]) {
      answer = max(answer, f[b][dis]);
      b = top[b];
      ++dis;
    }
    dis <<= 8;
    while (b ^ father[a]) {
      answer = max(answer, val[b] ^ dis);
      b = father[b];
      dis++;
    }
    printf("%d\n", answer);
  }
  return 0;
}

```