Yet Another Problem

题意翻译

你有一个长度为 $n$ 的整数序列 $a$。 你需要回答 $q$ 个独立的问题，每次询问如下： 给定 $l$ 和 $r$，你可以对序列做若干次操作（也可以不做），每次操作，你需要选择两个数 $L$ 与 $R$，其中必须满足 $l\le L\le R\le r$ 且 $R-L+1$ 为奇数。然后将 $a_L\sim a_R$ 的所有数改为 $a_L\sim a_R$ 的异或和，即 $a_L\oplus a_{L+1}\oplus \sim \oplus a_R$。 你的目标是将 $a_l\sim a_r$ 的所有数变为 $0$。每次询问完后，序列复原。 询问的答案即为最小操作数。如果总是不能达到目标，则答案为 $-1$。

题目描述

You are given an array $ a $ of $ n $ integers $ a_1, a_2, a_3, \ldots, a_n $ . You have to answer $ q $ independent queries, each consisting of two integers $ l $ and $ r $ . - Consider the subarray $ a[l:r] $ $ = $ $ [a_l, a_{l+1}, \ldots, a_r] $ . You can apply the following operation to the subarray any number of times (possibly zero)- 1. Choose two integers $ L $ , $ R $ such that $ l \le L \le R \le r $ and $ R - L + 1 $ is odd. 2. Replace each element in the subarray from $ L $ to $ R $ with the XOR of the elements in the subarray $ [L, R] $ . - The answer to the query is the minimum number of operations required to make all elements of the subarray $ a[l:r] $ equal to $ 0 $ or $ -1 $ if it is impossible to make all of them equal to $ 0 $ . You can find more details about XOR operation [here](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ $ (1 \le n, q \le 2 \cdot 10^5) $ — the length of the array $ a $ and the number of queries. The next line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ $ (0 \le a_i \lt 2^{30}) $ — the elements of the array $ a $ . The $ i $ -th of the next $ q $ lines contains two integers $ l_i $ and $ r_i $ $ (1 \le l_i \le r_i \le n) $ — the description of the $ i $ -th query.

输出格式

For each query, output a single integer — the answer to that query.

输入输出样例

输入样例 #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

说明

In the first query, $ l = 3, r = 4 $ , subarray = $ [3, 3] $ . We can apply operation only to the subarrays of length $ 1 $ , which won't change the array; hence it is impossible to make all elements equal to $ 0 $ . In the second query, $ l = 4, r = 6 $ , subarray = $ [3, 1, 2] $ . We can choose the whole subarray $ (L = 4, R = 6) $ and replace all elements by their XOR $ (3 \oplus 1 \oplus 2) = 0 $ , making the subarray $ [0, 0, 0] $ . In the fifth query, $ l = 1, r = 6 $ , subarray = $ [3, 0, 3, 3, 1, 2] $ . We can make the operations as follows: 1. Choose $ L = 4, R = 6 $ , making the subarray $ [3, 0, 3, 0, 0, 0] $ . 2. Choose $ L = 1, R = 5 $ , making the subarray $ [0, 0, 0, 0, 0, 0] $ .