给定一个数组 $$$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]$$$。