A. Евгений и массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

У Евгения есть массив a = a1, a2, ..., an, состоящий из n целых чисел. Каждое число ai равно или 1, или -1. Также есть m запросов:

  • Запрос номер i представляется в виде пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n).
  • Ответом на запрос будет число 1, если можно так переставить элементы массива a, что сумма ali + ali + 1 + ... + ari = 0, в противном случае ответом на запрос будет число 0.

Помогите Евгению, ответьте на все его запросы.

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

В первой строке записаны целые числа n и m (1 ≤ n, m ≤ 2·105). Во второй строке записаны n целых чисел a1, a2, ..., an (ai = -1, 1). В следующих m строках заданы запросы Евгения. В i-той строке записаны целые числа li, ri (1 ≤ li ≤ ri ≤ n).

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

Выведите m целых чисел — ответы на запросы Евгения в порядке их следования во входных данных.

Примеры
Входные данные
2 3
1 -1
1 1
1 2
2 2
Выходные данные
0
1
0
Входные данные
5 5
-1 1 1 1 -1
1 1
2 3
3 5
2 5
1 5
Выходные данные
0
1
0
1
0