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

Автор:Михалев Ю.   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 5 ⋅ 104

1 ≤ M ≤ 5 ⋅ 104

1 ≤ li ≤ ri ≤ N

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

Стандартный вход Стандартный выход
1
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
2
5 4
1 1 -1 1 1
1 5
4 5
3 3
2 2
-1
1
-1
1
3
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

0.147s 0.009s 13