Вам дан массив \(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\) на XOR элементов в подмассиве \([L, R]\).
- Ответом на запрос является минимальное количество операций, необходимых для того, чтобы все элементы подмассива \(a[l:r]\) стали равны \(0\), или \(-1\), если невозможно сделать их все равными \(0\).
Более подробную информацию об операции XOR можно найти здесь.
Примечание
В первом запросе, \(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]\). Мы можем выполнить следующие операции:
- Выбираем \(L = 4, R = 6\), делая подмассив \([3, 0, 3, 0, 0, 0]\).
- Выбираем \(L = 1, R = 5\), делая подмассив \([0, 0, 0, 0, 0, 0]\).