CF840E.In a Trap

Lech got into a tree consisting of n vertices with a root in vertex number 1. At each vertex i written integer a__i. He will not get out until he answers q queries of the form u v. Answer for the query is maximal value 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 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.

莱赫被困在一棵包含 $n$ 个顶点的树中，树根为编号为 1 的顶点。每个顶点 $i$ 上写有一个整数 $a_i$。他只有回答完 $q$ 个形如 $u\ v$ 的查询后才能脱身。对于每个查询，答案是路径 $u \to v$（包含端点 $u$ 和 $v$）上所有顶点 $i$ 中表达式

的最大值，其中 $\text{dist}(i,\,v)$ 表示从顶点 $i$ 到顶点 $v$ 的路径上的边数。题目保证顶点 $u$ 是顶点 $v$ 的祖先。莱赫的口味非常独特：他认为一个顶点是其自身的祖先。

请帮助莱赫脱身。

表达式 表示对数字 $x$ 和 $y$ 进行按位异或（XOR）运算。

注意：若顶点 $u$ 位于从根节点到顶点 $v$ 的路径上，则称顶点 $u$ 是顶点 $v$ 的祖先。

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 _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 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.

输入数据的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 5\cdot10^4$，$1 \leq q \leq 150\,000$）—— 分别表示树中顶点的数量和查询的数量。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$0 \leq a_i \leq n$）—— 各顶点上的数值。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u,\,v \leq n$）—— 描述树中的边。

保证所给图是一棵树。

接下来的 $q$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u,\,v \leq n$）—— 描述各次查询。保证顶点 $u$ 是顶点 $v$ 的祖先。

Output q lines — answers for a queries.

输出 q 行——各查询的答案。