D. Очередная задача
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$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]$$$. Вы можете применить следующую операцию к подмассиву любое количество раз (возможно, нулевое).
    1. Выберите два целых числа $$$L$$$, $$$R$$$ таких, что $$$l \le L \le R \le r$$$ и $$$R - L + 1$$$ является нечетным.
    2. Замените каждый элемент в подмассиве от $$$L$$$ до $$$R$$$ на XOR элементов в подмассиве $$$[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$$$.

В $$$i$$$-й из следующих $$$q$$$ строк содержится два целых числа $$$l_i$$$ и $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$  — описание $$$i$$$-го запроса.

Выходные данные

Для каждого запроса выведите одно целое число  — ответ на этот запрос.

Пример
Входные данные
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
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]$$$.