← 返回题目列表

AtCoder · code_festival_china_j

J. 异或

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

问题

Yu喜欢按位与运算和大数。 Yu的朋友Yihuo喜欢按位异或运算和小数。他们是好朋友,每当有人给他们发送一系列号码作为礼物时,他们就会互相分享这些号码。

对于非负整数数组 p_1, p_2, ..., p_k,让 D 是数组中所有数字之间按位与的结果 (p_1\rm{\ AND\ }p_2\rm{\ AND\ }...\rm{\ AND\ }p_k),并让 X 是数组中所有数字之间按位异或的结果 (p_1\rm{\ XOR\ }p_2\rm{\ XOR\ }...\rm{\ XOR\ }p_k)。 Yu 的满意度值 p_1, p_2, ..., p_k is D,亦货对同一个数字数组的满意度值为 -X (注意,亦火爱小数。越少 X 就是,愈火愈满足。)

每当他们收到非负整数数组时 p_1, p_2, ..., p_k 作为礼物,他们将阵从中间切开,宇得到前半部分,亦火得到后半部分。 他们切割数组的位置被确定为最大化每个数组的每个满意度值的总和。更准确地说,他们在 i内的第一个数字 1 \leq i < k,最大化 Yu 的满意度值之和 p_1, p_2, ..., p_i 和亦货的满意度值 p_{i+1}, p_{i+2}, ..., p_k.

您将获得 N 元素非负整数数组 A 和 Q 查询次数。的 j-第一个查询询问“当我们给予时,他们的满意度值的总和是多少 A_{l_j}, A_{l_j+1}, ..., A_{r_j} 致于与亦火”。您的任务是按给定顺序回答所有查询。

请注意,每个查询都由 2 整数 l_j, r_j (1 \leq l_j < r_j \leq N),但这些整数不是直接给出的。你必须计算那些 2 来自最后一个查询答案的整数,如输入部分所述。这意味着您必须按给定顺序计算查询的答案。


输入

N Q
A_1 A_2 ... A_N
l'_1 r'_1
l'_2 r'_2
:
l'_Q r'_Q
  • 在第一行,您将得到两个整数 N (2 \leq N \leq 10^5), Q (1 \leq Q \leq 10^5) 以空格分隔,数组中元素的数量 A 和查询次数分别。
  • 在第二行,您将得到 N 由空格分隔的整数。的 i-th (1 \leq i \leq N) 整数是 A_i (0 \leq A_i < 2^{31}).
  • 正在关注 Q 行是查询的信息。的 j-th (1 \leq j \leq Q) 行包含 2 整数 l'_j (1 \leq l'_j \leq N), r'_j (1 \leq r'_j \leq N) 以空格分隔。

计算 l_j, r_j,查询中的确切整数如下。

  • l_1 = l'_1, r_1 = r'_1
  • 对于所有 j 满足 2 ≦ j ≦ Q,让 m_{j - 1} 是问题的答案 (j - 1)第一个查询。
    • l_j = ((l'_j + \|m_{j - 1}\|)\rm{\ MOD\ }N) + 1
    • r_j = ((r'_j + \|m_{j - 1}\|)\rm{\ MOD\ }N) + 1

请注意,每个答案都可能是负数,即 m_{j - 1} 用于获取 l_j 和 r_j。 可以保证 1 \leq l_j < r_j \leq N 成立。

输出

输出 Q 行。的 j-th (1 \leq j \leq Q) 行应包含以下问题的答案 j-第一个查询。 确保在输出末尾插入换行符。


输入示例 1

7 4
7 3 5 4 6 3 1
2 5
2 5
3 4
5 1

输出示例 1

-1
2
2
5

每个查询的答案如下。

  • 对于第一个查询, l_1 = 2, r_1 = 5。 数字数组 3, 5, 4, 6 将被分离为 3, 5 和 4, 6,提供 Yu 的满意度值 3 和 5 = 1、亦货满意度值 -(4 异或 6) = -2,总结为 -1.
  • 对于第二个查询, l_2 = (2 + \|-1\|) 模组 7 + 1 = 4, r_2 = (5 + \|-1\|) 模组 7 + 1 = 7。 数组 4, 6, 3, 1 将被分离为 4, 6 和 3, 1,提供 Yu 的满意度值 4 和 6 = 4 和亦火的满意度值 -(3 异或 1) = -2,总结为 2.
  • 对于第三个查询, l_3 = (3 + \|2\|) 模组 7 + 1 = 6, r_3 = (4 + \|2\|) 模组 7 + 1 = 7。 数组 3, 1 只能分隔为 3 和 1,提供 Yu 的满意度值 3 和亦火的满意度值 -1,总结为 2.
  • 对于第四个查询, l_4 = (5 + \|2\|) 模组 7 + 1 = 1, r_4 = (1 + \|2\|) 模组 7 + 1 = 4。 数组 7, 3, 5, 4 将被分离为 7 和 3, 5, 4,提供 Yu 的满意度值 7 和亦火的满意度值 -(3 异或 5 异或 4) = -2,总结为 5.

输入示例 2

20 30
1 4 3 6 9 9 6 7 5 3 5 4 9 4 1 2 14 5 11 1
14 18
4 15
2 10
3 13
20 15
7 12
18 10
9 15
20 12
5 7
6 10
8 12
4 14
17 11
15 16
17 7
20 13
8 9
14 17
13 16
5 6
4 11
5 7
4 6
12 16
16 15
13 16
2 7
8 15
10 16

输出示例 2 每个查询的

-4
-1
0
-2
-1
-4
-1
4
3
-1
3
-2
6
3
10
5
1
-2
-1
-5
1
-6
-4
-1
-4
0
-9
4
3
2

的 l_i, r_i 如下。

14 18
9 20
4 12
4 14
3 18
9 14
3 15
11 17
5 17
9 11
8 12
12 16
7 17
4 18
19 20
8 18
6 19
10 11
17 20
15 18
11 12
6 13
12 14
9 11
14 18
1 20
14 17
12 17
13 20
14 20