У Евгения есть массив a = a1, a2, ..., an, состоящий из n целых чисел. Каждое число ai равно или 1, или -1. Также есть m запросов:
- Запрос номер i представляется в виде пары целых чисел li, ri (1 ≤ li ≤ ri ≤ n).
- Ответом на запрос будет число 1, если можно так переставить элементы массива a, что сумма ali + ali + 1 + ... + ari = 0, в противном случае ответом на запрос будет число 0.
Помогите Евгению, ответьте на все его запросы.
Выходные данные
Выведите m целых чисел — ответы на запросы Евгения в порядке их следования во входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
1 -1
1 1
1 2
2 2
|
0
1
0
|
|
2
|
5 5
-1 1 1 1 -1
1 1
2 3
3 5
2 5
1 5
|
0
1
0
1
0
|