给你一个包含 n 个整数 ai 和 m 个查询的数组。每个查询由两个整数 (lj, rj) 描述。
让我们定义函数 $$f(u,v) = u \oplus (u+1) \oplus \ldots \oplus v$$。该函数仅针对 u ≤ v 定义。
对于每个查询,打印函数 f(ax, ay) 在所有 lj ≤ x、y ≤ rj、ax ≤ ay 上的最大值。
输入
第一行包含两个整数 n, m (1 ≤ n ≤ 5·104, 1 ≤ m ≤ 5·103) — 数组的大小和查询的数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 106) — 数组 a 的元素。
接下来的 m 行每行包含两个整数 lj, rj (1 ≤ lj ≤ rj ≤ n) – 第 j 个查询的参数。
输出
对于每个查询,在单独的行上打印值 aj — 函数 f(ax, ay) 在所有 lj ≤ x、y ≤ rj、ax ≤ ay 上的最大值。
示例
输入 #1
6 3 1 2 3 4 5 6 1 6 2 5 3 4
输出 #1
7 7 7
输入 #2
1 1 1 1 1
输出 #2
1
输入 #3
6 20 10 21312 2314 214 1 322 1 1 1 2 1 3 1 4 1 5 1 6 2 2 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 4 4 5 4 6 5 5 5 6 6 6
输出 #3
10 21313 21313 21313 21313 21313 21312 21313 21313 21313 21313 2314 2315 2315 214 215 323 1 323 322