← 返回题目列表

Codeforces · 840/E

E. 陷入陷阱

中文机器翻译题面 查看原题

Lech 进入一棵由 n 个顶点组成的树,根在顶点号 1 中。在每个顶点我写入整数 ai。在回答 u v 形式的 q 个查询之前,他不会出去。查询的答案是从 u 到 v 的路径上的所有顶点 i(包括 u 和 v)中的最大值 $$a_i \oplus dist(i,v)$$,其中 dist(i, v) 是从 i 到 v 的路径上的边数。还保证顶点 u 是顶点 v 的祖先。Leha 的品味非常单一:他相信顶点是其自身的祖先。

帮助Leha 出去。

表达式 $$x \oplus y$$ 表示数字 x 和 y 的按位异或。

请注意,如果顶点 u 位于从根到顶点 v 的路径上,则顶点 u 是顶点 v 的祖先。

输入

输入数据的第一行包含两个整数 n 和 q (1 ≤ n ≤ 5·104, 1 ≤ q ≤ 150 000) — 分别是树中的顶点数和查询数。

下一行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ n) — 顶点上的数字。

接下来的 n - 1 行中的每一行都包含两个整数 u 和 v (1 ≤ u, v ≤ n) — 树中边的描述。

保证给定的图是一棵树。

接下来的 q 行包含两个整数 u 和 v (1 ≤ u, v ≤ n) — 查询的描述。保证顶点 u 是顶点 v 的祖先。

输出

输出 q 行 — 查询的答案。

示例

输入 #1

5 3
0 3 2 1 4
1 2
2 3
3 4
3 5
1 4
1 5
2 4

输出 #1

3
4
3

输入 #2

5 4
1 2 3 4 5
1 2
2 3
3 4
4 5
1 5
2 5
1 4
3 3

输出 #2

5
5
4
3