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] $ .

**题目大意：**

你有一个长度为 $ 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 $。

**输入输出数据格式：**

**输入格式：**

第一行包含两个整数 $ 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 $ 行，每行包含两个整数 $ l_i $ 和 $ r_i $ $ (1 \le l_i \le r_i \le n) $ — 第 $ i $ 个查询的描述。

**输出格式：**

对于每个查询，输出一个整数 — 该查询的答案。**题目大意：** 你有一个长度为 $ 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 $。 **输入输出数据格式：** **输入格式：** 第一行包含两个整数 $ 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 $ 行，每行包含两个整数 $ l_i $ 和 $ r_i $ $ (1 \le l_i \le r_i \le n) $ — 第 $ i $ 个查询的描述。 **输出格式：** 对于每个查询，输出一个整数 — 该查询的答案。