← 返回题目列表

Codeforces · 1747/D

D. 又一个问题

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

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 个整数 $$$a_1、a_2、a_3、\ldots、a_n$$$。

您必须回答 $$$q$$$ 独立查询,每个查询由两个整数 $$$l$$$ 和 $$$r$$$ 组成。

- 考虑子数组 $$$a[l:r]$$$ $$$=$$$ $$$[a_l, a_{l+1}, \ldots, a_r]$$$。您可以对子数组应用以下操作任意次数(可能为零) - 选择两个整数 $$$L$$$、$$$R$$$,使得 $$$l \le L \le R \le r$$$ 和 $$$R - L + 1$$$ 为奇数。 将子数组中 $$$L$$$ 到 $$$R$$$ 中的每个元素替换为子数组 $$$[L, R]$$$ 中元素的异或。
- 查询的答案是使子数组 $$$a[l:r]$$$ 的所有元素等于 $$$0$$$ 或 $$$-1$$$(如果不可能使所有元素都等于 $$$0$$$)所需的最少操作数。

您可以在此处找到有关 XOR 运算的更多详细信息。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 2 \cdot 10^5)$$$ — 数组 $$$a$$$ 的长度和查询次数。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \lt 2^{30})$$$ — 数组 $$$a$$$ 的元素。

接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ — 第 $$$i$$$ 查询的描述。

输出

对于每个查询,输出一个整数 - 该查询的答案。

示例

输入 #1

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

输出 #1

-1
1
1
-1
2
0

注意

在第一个查询中,$$$l = 3,r = 4$$$,子数组 = $$$[3, 3]$$$。我们只能对长度为$$$1$$$的子数组进行操作,这不会改变数组;因此不可能使所有元素都等于$$$0$$$。

在第二个查询中,$$$l = 4,r = 6$$$,子数组 = $$$[3, 1, 2]$$$。我们可以选择整个子数组 $$$(L = 4, R = 6)$$$ 并通过 XOR $$$(3 \oplus 1 \oplus 2) = 0$$$ 替换所有元素,从而使子数组 $$$[0, 0, 0]$$$。

在第五个查询中,$$$l = 1,r = 6$$$,子数组 = $$$[3, 0, 3, 3, 1, 2]$$$。我们可以进行如下操作:

1. 选择$$$L = 4, R = 6$$$,使子数组$$$[3, 0, 3, 0, 0, 0]$$$。
2. 选择$$$L = 1, R = 5$$$,使子数组$$$[0, 0, 0, 0, 0, 0]$$$。