Катя и массив (10 баллов)

- Как, это опять Вы?
Студентка Катя молча потупила взор.
- И что, у Вас прибавилось знаний с прошлого раза?
- Я учииилааа...
- Что именно Вы учили, Екатерина?
- Массиииивыыыы...
- Хорошо, вот Вам задачка. Есть массив из n элементов, заполненный целыми числами. И есть m пар индексов L_i и R_i, для каждой пары надо определить, можно ли переставить элементы массива таким образом, чтобы сумма элементов с L_i-го по R_i-й равнялась заданному числу.
- Слооожнооо...
- Ну хорошо, упростим... чтобы сумма равнялась нулю.
- Всё равно слооожнооо...
- Хорошо упростим ещё: элементы массива равны либо 1, либо -1.
- Так ещё сложнее... там числа отрицааательные...

Положите конец страданиям Кати и напишите за неё программу.

Входные данные: В первой строке записаны целые числа n и m (1≤n, m≤100000). Во второй строке записаны n целых чисел, разделённых пробелами, каждое из которых равно либо 1, либо -1. В следующих m строках "вопросы", пары индексов, задающие интервалы. В i-той строке записаны целые числа L_i и R_i (1≤L_i≤R_i≤n).

Выходные данные: m целых чисел — ответы на вопросы в порядке их следования во входных данных, по одному в строке. Число 1 означает, что перестановка возможна, 0 - что невозможна.