CF1747D.Yet Another Problem

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.

给你一个包含 $n$ 个整数 $a_1, a_2, a_3, \ldots, a_n$ 的数组 $a$。

你需要回答 $q$ 个相互独立的查询，每个查询由两个整数 $l$ 和 $r$ 组成。

• 考虑子数组 $a[l:r] = [a_l, a_{l+1}, \ldots, a_r]$。你可以对该子数组执行以下操作任意多次（包括零次）：
  1. 选择两个整数 $L$、$R$，满足 $l \le L \le R \le r$，且 $R - L + 1$ 为奇数；
  2. 将子数组 $[L, R]$ 中的每个元素替换为该子数组 $[L, R]$ 内所有元素的异或（XOR）值。
• 查询的答案为：使子数组 $a[l:r]$ 中所有元素均变为 $0$ 所需的最少操作次数；若无法使所有元素变为 $0$，则答案为 $-1$。

关于异或（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.

第一行包含两个整数 $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$ 个查询的描述。

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

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

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

在第一次查询中，$l = 3, r = 4$，子数组为 $[3, 3]$。我们只能对长度为 $1$ 的子数组执行操作，而该操作不会改变数组；因此无法使所有元素变为 $0$。

在第二次查询中，$l = 4, r = 6$，子数组为 $[3, 1, 2]$。我们可以选择整个子数组（即 $L = 4, R = 6$），并将所有元素替换为其异或值 $(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]$。