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