← 返回题目列表

Codeforces · 620/F

F. 段上的异或

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

给你一个包含 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