Задача C. Скучные дни ≡

Условие

Васе скучно. Чтобы развлечь себя, он стал отмечать скучные дни числом −1, а обычные числом 1. Теперь Вася называет промежуток с l по r дни включительно скучным, если в него входит нечетное число скучных дней.

Чтобы не дать Васе умереть от скуки, вы должны срочно научиться отвечать на следующий вопрос: является ли промежуток с l по r день включительно скучным?

Формат входных данных

Первая строка входных данных содержит два целых числа N — количество дней и M — количество запросов.

Вторая строка содержит N чисел: −1, если i-ый день был скучным, и 1 иначе.

Следующие M строк содержат запросы вида: l_i r_i

Формат выходных данных

Выходные данные должны содержать M строк - ответы на запросы

В i−й строке необходимо вывести −1, если промежуток с l_i по r_i дни включительно считается скучным, и 1 в противном случае

Ограничения

1 ≤ N ≤ 5 ⋅ 10⁴

1 ≤ M ≤ 5 ⋅ 10⁴

1 ≤ l_i ≤ r_i ≤ N

Примеры тестов

6 6
1 -1 -1 1 1 -1
1 2
1 6
2 3
4 5
3 6
1 5

-1
-1
1
1
1
1

5 4
1 1 -1 1 1
1 5
4 5
3 3
2 2

-1
1
-1
1

10 5
-1 -1 -1 1 -1 -1 1 1 -1 -1
1 3
1 4
3 5
8 10
3 9

-1
-1
1
1
1