Eugeny has array a = a_1, a_2, ..., a_{n}, consisting of n integers. Each integer a_{i} equals to -1, or to 1. Also, he has m queries:  Query number i is given as a pair of integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n).  The response to the query will be integer 1, if the elements of array a can be rearranged so as the sum a_{l}_{i} + a_{l}_{i} + 1 + ... + a_{r}_{i} = 0, otherwise the response to the query will be integer 0. 

Help Eugeny, answer all his queries.


-----Input-----

The first line contains integers n and m (1 ≤ n, m ≤ 2·10^5). The second line contains n integers a_1, a_2, ..., a_{n} (a_{i} = -1, 1). Next m lines contain Eugene's queries. The i-th line contains integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n).


-----Output-----

Print m integers — the responses to Eugene's queries in the order they occur in the input.


-----Examples-----
Input
2 3
1 -1
1 1
1 2
2 2

Output
0
1
0

Input
5 5
-1 1 1 1 -1
1 1
2 3
3 5
2 5
1 5

Output
0
1
0
1
0

Difficulty: interview

Starter code:

Solutions:
n, m = map(int, input().split())
t = input()
a, b = t.count('1'), t.count('-')
t = ['0'] * m
c = 2 * min(a - b, b)
for i in range(m):
    l, r = map(int, input().split())
    r -= l
    if r & 1 and r < c: t[i] = '1'
print('\n'.join(t))

import sys
import math

import sys
import math
  
n, m = [int(x) for x in (sys.stdin.readline()).split()]
st = sys.stdin.readline()

res = 0
i = 0
vi = 0
while(i < n):
    if(st[vi] == '-'):
        res += 1
        vi += 3
    else:
        vi += 2
        
    i += 1
    
vmin = min(res, n - res)  
vmin *= 2
  
for i in range(m):
    l, r = [int(x) for x in (sys.stdin.readline()).split()]
    k = r - l + 1
    if(k % 2 != 0):
        sys.stdout.write("0\n")
    else:
        if(k <= vmin):
            sys.stdout.write("1\n")
        else:
            sys.stdout.write("0\n")



n, m = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
mo = a.count(-1)
po = n - mo
ans = []
for i in range(m):
	a, b = [int(x) for x in input().split()]
	l = (b - a + 1)
	if l % 2:
		ans.append('0')
	elif po < l // 2 or mo < l // 2:
		ans.append('0')
	else:
		ans.append('1')
print('\n'.join(ans))


def main():
    n, m = map(int, input().split())
    a = input().split().count('1')
    if a > n - a:
        a = n - a
    res = []
    for _ in range(m):
        l, r = map(int, input().split())
        r -= l
        res.append(('0', '1')[r & 1 and a * 2 >= r + 1])
    print('\n'.join(res))


def __starting_point():
    main()
__starting_point()

def main():
    n, m = map(int, input().split())
    a = input().count('-')
    if a > n - a:
        a = n - a
    res = []
    for _ in range(m):
        l, r = map(int, input().split())
        r -= l
        res.append(('0', '1')[r & 1 and a * 2 >= r + 1])
    print('\n'.join(res))


def __starting_point():
    main()
__starting_point()


s = input().split()
n = int(s[0])
m = int(s[1])
mp = list(map(int,input().split()))
neg = 0
pos = 0
for k in mp:
    if k==-1:
        neg+=1
    else:
        pos+=1

mine = min(neg,pos)
ans = ""
while m>0:
    m-=1
    st = input().split()
    l = int(st[0])
    r = int(st[1])
    dif = r-l+1
    if dif%2==0 and dif//2<=mine:
        ans+="1\n"
    else:
        ans+="0\n"
print(ans)


n, m = map(int, input().split())
a = list(map(int, input().split()))
a_plus = a.count(1)
a_minus = a.count(-1)
s = ''
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    s += '0\n' if length % 2 or length // 2 > a_plus or length // 2 > a_minus else '1\n'
print(s)

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a_min = min(a.count(1), a.count(-1))
s = ''
for i in range(m):
    l, r = list(map(int, input().split()))
    length = r - l + 1
    s += '0\n' if length % 2 or length // 2 > a_min else '1\n'
print(s)


n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
a_plus = a.count(1)
a_min = min(a_plus, n - a_plus)
s = ''
for i in range(m):
    l, r = list(map(int, input().split()))
    length = r - l + 1
    s += '0\n' if length % 2 or length // 2 > a_min else '1\n'
print(s)


n, m = map(int, input().split())
a = list(map(int, input().split()))
a_plus = a.count(1)
a_min = min(a_plus, n - a_plus)
res = []
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    res += ['0'] if length % 2 or length // 2 > a_min else ['1']
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus)
res = []
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    res += ['0'] if length % 2 or length // 2 > a_min else ['1']
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = []
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    res += ['0'] if length % 2 or length > a_min else ['1']
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = []
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    res.append('0' if length % 2 or length > a_min else '1')
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = ['0'] * m
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    res[i] = '0' if length % 2 or length > a_min else '1'
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = []
append = res.append
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    append('0' if length % 2 or length > a_min else '1')
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = []
append = res.append
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    if length % 2 or length > a_min:
        append('0')
    else:
        append('1')
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = []
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    res.append('0' if length > a_min or length % 2 else '1')
print('\n'.join(res))

n, m = map(int, input().split())
a_plus = input().split().count('1')
a_min = min(a_plus, n - a_plus) * 2
res = ['1'] * m
for i in range(m):
    l, r = map(int, input().split())
    length = r - l + 1
    if length > a_min or length % 2:
        res[i] = '0'
print('\n'.join(res))

N, M = list(map(int, input().split()))

A = input().split()

count_one = A.count('1')

solution = []

queries = []
for i in range(M):
    Li, Ri = list(map(int, input().split()))
    if ( (Ri-Li+1)%2 == 0 and
         (Ri-Li+1)//2 <= min(count_one, N-count_one)):
        solution.append('1')
        continue
    else:
        solution.append('0')

print('\n'.join(solution))


n, m = list(map(int, input().split()))
n_one = len(input().strip()) - (2 * n - 1)
less = min(n_one, n - n_one) * 2
res = [None] * m

for i in range(0, m):
    l, r = list(map(int, input().split()))
    q = r - l + 1
    res[i] = '1' if q % 2 == 0 and q <= less else '0'

print('\n'.join(res))


n, m = list(map(int, input().split()))
a = input().split().count('1')
b = min(a, n - a) * 2
ans = []
for i in range(m):
    l, r = list(map(int, input().split()))
    length = r - l + 1
    ans += ['0'] if length % 2 or length > b else ['1']
print('\n'.join(ans))


n, m = map(int, input().split())
a = input().split()
x = a.count("-1")
ans = ""
for _ in range(m):
  l, r = map(int, input().split())
  if (r-l) % 2 == 1 and min(x, n-x) >= (r-l+1)//2:
    ans += "1\n"
  else:
    ans += "0\n"
print(ans)

import sys

def main():
    (n, m) = list(map(int, sys.stdin.readline().split(' ')))
    a = list(map(int, sys.stdin.readline().split(' ')))
    ones = 0
    negs = 0
    for ai in a:
        if ai == 1:
            ones += 1
        else:
            negs += 1
    for i in range(m):
        (l, r) = list(map(int, sys.stdin.readline().split(' ')))
        count = r - l + 1
        if count % 2 != 0:
            sys.stdout.write("0\n")
        else:
            if ones >= count // 2 and negs >= count // 2:
                sys.stdout.write("1\n")
            else:
                sys.stdout.write("0\n")
main()


n,m = list(map(int,input().split()))
a = list(map(int, input().split()))
b = a.count(1)
c = min(b,n-b)
s = ''
for i in range(m):
    left,right = list(map(int, input().split()))
    length = right - left + 1
    if length % 2 or length //2 > c:
        s += "0\n"
    else:
        s += "1\n"
print(s)


#!/usr/bin/env python3
#! -*- coding: utf-8 -*-
from sys import stdin, stdout

def main():
	input = stdin.readline
	print = stdout.write
	n, m = map(int, input().split())
	a = [int(i) for i in input().split()]
	pos = sum(x > 0 for x in a)
	neg = n - pos
	for _ in range(m):
		L, R = map(int, input().split())
		length = R - L + 1
		if length % 2 == 0 and pos >= length // 2 and neg >= length // 2:
			print('1\n')
		else:
			print('0\n')


def __starting_point():
	main()
__starting_point()