#include <bits/stdc++.h>
using namespace std;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
void chmax(T &x, const T y) {
  x = (x > y ? x : y);
}
template <typename T>
void chmin(T &x, const T y) {
  x = (x < y ? x : y);
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
void add(T &x, const int &y) {
  x = (x + y >= MOD ? x + y - MOD : x + y);
}
long long qpower(long long x, long long e, int mod = MOD) {
  long long ans = 1;
  if (e < 0) {
    puts("error");
    exit(666);
  }
  while (e) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int N = 5e4 + 10;
namespace Trie {
int id = 1, son[N * 17][2];
void clear() {
  for (int i = (0), I = (id); i <= I; i++) son[i][0] = son[i][1] = 0;
  id = 1;
}
void insert(int num) {
  int now = 1;
  for (int i = (15), I = (0); i >= I; i--) {
    int wt = (num & (1ll << (i))) > 0;
    if (!son[now][wt]) son[now][wt] = ++id;
    now = son[now][wt];
  }
}
int ask(int num) {
  int now = 1, ans = 0;
  for (int i = (15), I = (0); i >= I; i--) {
    int wt = ((num & (1ll << (i))) > 0) ^ 1;
    if (!son[now][wt])
      wt ^= 1;
    else
      ans += (1ll << (i));
    now = son[now][wt];
    assert(now > 0);
  }
  return ans;
}
};  // namespace Trie
int ff[N];
vector<int> to[N];
int n, hh[N][200], a[N], T = 256, dep[N], anc[N];
void pre(int x, int fa) {
  ff[x] = fa;
  dep[x] = dep[fa] + 1;
  Trie::clear();
  int now = x;
  for (int dis = 0; dis < T and now > 0; dis++, now = ff[now])
    Trie::insert(a[now] ^ dis);
  anc[x] = now;
  assert(dep[x] - dep[anc[x]] == T or anc[x] == 0);
  for (int t = (0), I = (n / T); t <= I; t++) hh[x][t] = Trie::ask(t * T);
  for (auto y : to[x])
    if (y != fa) pre(y, x);
}
void main() {
  n = qread();
  int q = qread();
  for (int i = (1), I = (n); i <= I; i++) a[i] = qread();
  for (int i = (2), I = (n); i <= I; i++) {
    int x = qread(), y = qread();
    to[x].push_back(y);
    to[y].push_back(x);
  }
  pre(1, 0);
  while (q--) {
    int y = qread(), x = qread(), ans = a[y] ^ (dep[x] - dep[y]), z = x;
    while (dep[z] - T + 1 >= dep[y])
      chmax(ans, hh[z][(dep[x] - dep[z]) / T]),
          z = anc[z], assert((dep[x] - dep[z]) % T == 0);
    while (dep[z] >= dep[y]) chmax(ans, a[z] ^ (dep[x] - dep[z])), z = ff[z];
    write2(ans);
  }
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
}

### Prompt

Your task is to create 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;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
void chmax(T &x, const T y) {
  x = (x > y ? x : y);
}
template <typename T>
void chmin(T &x, const T y) {
  x = (x < y ? x : y);
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
void add(T &x, const int &y) {
  x = (x + y >= MOD ? x + y - MOD : x + y);
}
long long qpower(long long x, long long e, int mod = MOD) {
  long long ans = 1;
  if (e < 0) {
    puts("error");
    exit(666);
  }
  while (e) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int N = 5e4 + 10;
namespace Trie {
int id = 1, son[N * 17][2];
void clear() {
  for (int i = (0), I = (id); i <= I; i++) son[i][0] = son[i][1] = 0;
  id = 1;
}
void insert(int num) {
  int now = 1;
  for (int i = (15), I = (0); i >= I; i--) {
    int wt = (num & (1ll << (i))) > 0;
    if (!son[now][wt]) son[now][wt] = ++id;
    now = son[now][wt];
  }
}
int ask(int num) {
  int now = 1, ans = 0;
  for (int i = (15), I = (0); i >= I; i--) {
    int wt = ((num & (1ll << (i))) > 0) ^ 1;
    if (!son[now][wt])
      wt ^= 1;
    else
      ans += (1ll << (i));
    now = son[now][wt];
    assert(now > 0);
  }
  return ans;
}
};  // namespace Trie
int ff[N];
vector<int> to[N];
int n, hh[N][200], a[N], T = 256, dep[N], anc[N];
void pre(int x, int fa) {
  ff[x] = fa;
  dep[x] = dep[fa] + 1;
  Trie::clear();
  int now = x;
  for (int dis = 0; dis < T and now > 0; dis++, now = ff[now])
    Trie::insert(a[now] ^ dis);
  anc[x] = now;
  assert(dep[x] - dep[anc[x]] == T or anc[x] == 0);
  for (int t = (0), I = (n / T); t <= I; t++) hh[x][t] = Trie::ask(t * T);
  for (auto y : to[x])
    if (y != fa) pre(y, x);
}
void main() {
  n = qread();
  int q = qread();
  for (int i = (1), I = (n); i <= I; i++) a[i] = qread();
  for (int i = (2), I = (n); i <= I; i++) {
    int x = qread(), y = qread();
    to[x].push_back(y);
    to[y].push_back(x);
  }
  pre(1, 0);
  while (q--) {
    int y = qread(), x = qread(), ans = a[y] ^ (dep[x] - dep[y]), z = x;
    while (dep[z] - T + 1 >= dep[y])
      chmax(ans, hh[z][(dep[x] - dep[z]) / T]),
          z = anc[z], assert((dep[x] - dep[z]) % T == 0);
    while (dep[z] >= dep[y]) chmax(ans, a[z] ^ (dep[x] - dep[z])), z = ff[z];
    write2(ans);
  }
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
}

```