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

Source: codeforces | Difficulty: EASY
Tags: Implementation


Solutions:
from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
a = list(map(int, stdin.readline().split()))
neg_count = 0
pos_count = 0
for i in a:
	if i == -1:
		neg_count += 1
	else:
		pos_count += 1
for i in range(m):
	(l, r) = map(int, stdin.readline().split())
	if l == r:
		stdout.write('0' + '\n')
	elif (r - l + 1) % 2 != 0 or neg_count < (r - l + 1) // 2 or pos_count < (r - l + 1) // 2:
		stdout.write('0' + '\n')
	else:
		stdout.write('1' + '\n')


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
su = abs(sum(l))
limit = n - su
ans = []
for _ in range(m):
	(l, r) = map(int, input().split())
	if (r - l) % 2 != 0 and r - l < limit:
		ans.append(1)
	else:
		ans.append(0)
for i in ans:
	print(i)


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()


import math

def main_function():
	output_list = []
	(n, m) = [int(i) for i in input().split(' ')]
	a = [int(i) for i in input().split(' ')]
	input_list = [[int(h) for h in input().split(' ')] for i in range(m)]
	count_negative_1 = 0
	count_positive_1 = 0
	for i in a:
		if i < 0:
			count_negative_1 += 1
		else:
			count_positive_1 += 1
	for i in input_list:
		if not (i[1] - i[0]) % 2:
			ans = 0
		elif (i[1] - i[0] + 1) // 2 <= count_negative_1 and (i[1] - i[0] + 1) // 2 <= count_positive_1:
			ans = 1
		else:
			ans = 0
		output_list.append(str(ans))
	return '\n'.join(output_list)
print(main_function())


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


from sys import stdin, stdout
(n, m) = [int(x) for x in stdin.readline().split()]
arr = [int(x) for x in stdin.readline().split()]
positive = arr.count(1)
negative = n - positive
mi = min(positive, negative)
ans = ''
while m > 0:
	(a, b) = [int(x) for x in stdin.readline().split()]
	if (b - a + 1) % 2 == 0 and mi >= (b - a + 1) / 2:
		print(1)
	else:
		print(0)
	m -= 1


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
from collections import Counter
(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
cnt = Counter()
for v in arr:
	cnt[v] += 1
for i in range(m):
	(l, r) = map(int, input().split())
	dist = r - l + 1
	if dist % 2 == 1 or min(cnt[-1], cnt[1]) < dist // 2:
		print(0)
	else:
		print(1)


import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
count_negs = 0
for el in arr:
	if el == -1:
		count_negs += 1
count_pos = n - count_negs
for i in range(q):
	(l, r) = map(int, input().split())
	dist = r - l + 1
	if dist % 2 == 1:
		print(0)
	elif count_negs >= dist // 2 and count_pos >= dist // 2:
		print(1)
	else:
		print(0)


(n, m) = 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) = 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_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) = map(int, input().split())
l = list(input().split())
(p, q) = (0, 0)
c = ''
for x in l:
	if x == '1':
		p += 1
	else:
		q += 1
for i in range(m):
	(a, b) = map(int, input().split())
	if (b - a + 1) % 2 == 0 and p >= (b - a + 1) // 2 and (q >= (b - a + 1) // 2):
		c += '1\n'
	else:
		c += '0\n'
print(c)


import sys

def minp():
	return sys.stdin.readline().strip()

def mints():
	return map(int, minp().split())

def solve():
	(n, m) = mints()
	a = list(mints())
	ones = a.count(1)
	mones = n - ones
	for i in range(m):
		(l, r) = mints()
		c = r - l + 1
		if c % 2 == 1:
			print(0)
		elif c // 2 <= ones and c // 2 <= mones:
			print(1)
		else:
			print(0)
solve()


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


I = lambda : map(int, input().split())
(n, m) = I()
arr = I()
(one, m_one) = (0, 0)
for i in arr:
	if i == -1:
		m_one += 1
	else:
		one += 1
arr = []
for i in range(m):
	(l, r) = I()
	temp = r - l + 1
	if temp % 2 == 0 and one >= temp // 2 and (m_one >= temp // 2):
		arr.append(1)
	else:
		arr.append(0)
print(*arr)


X = list(map(int, input().split()))
Negative = input().count('-')
Positive = X[0] - Negative
Answer = ''
for i in range(X[1]):
	Temp = list(map(int, input().split()))
	Number = Temp[1] - Temp[0] + 1
	if Number % 2 == 0 and Number // 2 == min(Number // 2, Negative, Positive):
		Answer += '1\n'
	else:
		Answer += '0\n'
print(Answer)


import sys
(n, m) = map(int, sys.stdin.readline().split())
neg = sorted(list(map(int, sys.stdin.readline().split()))).count(-1)
d = min(neg, n - neg) * 2
for i in range(m):
	(l, r) = map(int, sys.stdin.readline().split())
	if r + 1 - l <= d and l != r and ((r - l) % 2 != 0):
		print(1)
	else:
		print(0)


(n, m) = map(int, input().split())
x = [int(w) for w in input().split()]
p = x.count(1)
t = n - p
s = ''
for j in range(m):
	(l, r) = map(int, input().split())
	e = r - l + 1
	if e % 2 or min(p, t) < e // 2:
		s += '0\n'
	else:
		s += '1\n'
print(s)


z = list(map(int, input().split()))
x = list(map(int, input().split()))
d = []
s = x.count(-1)
b = x.count(1)
for i in range(z[1]):
	c = 0
	f = list(map(int, input().split()))
	c = f[1] - f[0] + 1
	if c % 2 != 0:
		d.append(0)
	elif c // 2 <= s and c // 2 <= b:
		d.append(1)
	else:
		d.append(0)
for i in d:
	print(i)


(n, p) = map(int, input().split())
sumP = sumN = 0
for i in list(map(int, input().split())):
	if i == 1:
		sumP += 1
	else:
		sumN += 1
res = []
for i in range(p):
	(x, y) = map(int, input().split())
	res.append('1' if min(sumP, sumN) >= (y - x + 1) // 2 and (y - x) % 2 == 1 else '0')
print('\n'.join(res))


from math import *
from cmath import *
from itertools import *
from decimal import *
from fractions import *
from sys import *
from types import new_class
n = input().split()
cnt1 = cnt2 = 0
for x in input().split():
	if x == '1':
		cnt1 += 1
	else:
		cnt2 += 1
v0 = []
for _ in range(int(n[1])):
	l = input().split()
	r = int(l[1])
	k = int(l[0])
	if (r - k) % 2 and cnt1 >= (r - k + 1) // 2 and (cnt2 >= (r - k + 1) // 2):
		v0.append(1)
	else:
		v0.append(0)
for x in v0:
	print(x)


(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))


(n, m) = map(int, input().split())
l = input().split()
c = l.count('-1')
c = min(c, n - c)
res = ''
for i in range(m):
	(l, r) = map(int, input().split())
	l = r - l + 1
	if l % 2 == 0 and c >= l / 2:
		res += '1\n'
	else:
		res += '0\n'
print(res)


(n, m) = map(int, input().split())
list = [int(i) for i in input().split()]
(pos, neg) = (0, 0)
for i in range(n):
	if list[i] == 1:
		pos += 1
	else:
		neg += 1
ans = ''
for i in range(0, m):
	(l, r) = map(int, input().split())
	if (r - l + 1) % 2 == 0 and int((r - l + 1) / 2) <= pos and (int((r - l + 1) / 2) <= neg):
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


from math import *
from cmath import *
from itertools import *
from decimal import *
from fractions import *
from sys import *
from types import new_class
nm = input().split()
n = int(nm[0])
m = int(nm[1])
kol1 = 0
kolm1 = 0
v0 = []
a = input().split()
for i in range(n):
	if a[i] == '1':
		kol1 += 1
		continue
	kolm1 += 1
for i in range(m):
	b = input().split()
	b[0] = int(b[0])
	b[1] = int(b[1])
	if (b[1] - b[0] + 1) % 2 == 0 and (b[1] - b[0] + 1) // 2 <= kol1 and ((b[1] - b[0] + 1) // 2 <= kolm1):
		v0.append(1)
		continue
	v0.append(0)
for i in range(m):
	print(v0[i])


import math, itertools, fractions, heapq, collections, bisect, sys, queue, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return input()

def summarizeList(l):
	sl = sorted(l)
	a = sl[0]
	c = 1
	res = []
	for x in sl[1:]:
		if x == a:
			c += 1
		else:
			res.append([a, c])
			a = x
			c = 1
	res.append([a, c])
	return res

def main():
	(n, k) = LI()
	l = LI()
	sl = summarizeList(l)
	ans = []
	for _ in range(k):
		(a, b) = LI()
		x = b - a + 1
		if x % 2 == 1:
			ans.append(0)
		elif len(sl) == 1:
			ans.append(0)
		elif sl[0][1] >= x // 2 and sl[1][1] >= x // 2:
			ans.append(1)
		else:
			ans.append(0)
	for x in ans:
		print(x)
main()


(n, m) = map(int, input().split())
a = input()
menos_1 = a.count('-1')
mais_1 = n - menos_1
res = []
for _ in range(m):
	(l, r) = map(int, input().split())
	tam = r - l + 1
	if tam % 2 == 0:
		if menos_1 >= tam / 2 and mais_1 >= tam / 2:
			res.append('1')
		else:
			res.append('0')
	else:
		res.append('0')
print('\n'.join(res))


from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def smp():
	return map(str, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def remadd(x, y):
	return 1 if x % y else 0

def ceil(a, b):
	return (a + b - 1) // b

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
(n, m) = mp()
arr = lmp()
(a, b) = (arr.count(-1), arr.count(1))
for i in range(m):
	(l, r) = mp()
	d = r - l + 1
	if d % 2 == 0:
		print(1 if min(a, b) >= d // 2 else 0)
	else:
		print(0)


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')
main()


nm = input().split()
n = int(nm[0])
m = int(nm[1])
kol1 = 0
kolm1 = 0
v0and1 = []
a = input().split()
for i in range(n):
	if a[i] == '1':
		kol1 += 1
		continue
	kolm1 += 1
for i in range(m):
	b = input().split()
	b[0] = int(b[0])
	b[1] = int(b[1])
	if (b[1] - b[0] + 1) % 2 == 0 and (b[1] - b[0] + 1) // 2 <= kol1 and ((b[1] - b[0] + 1) // 2 <= kolm1):
		v0and1.append(1)
		continue
	v0and1.append(0)
for i in range(m):
	print(v0and1[i])


import sys
import math
from sys import stdin, stdout

def sieve(N):
	primeNumbers = [True] * (N + 1)
	primeNumbers[0] = False
	primeNumbers[1] = False
	i = 2
	while i * i <= N:
		j = i
		if primeNumbers[j]:
			while j * i <= N:
				primeNumbers[j * i] = False
				j += 1
		i += 1
	return primeNumbers

def getPrime(N):
	primes = sieve(N)
	result = []
	for i in range(len(primes)):
		if primes[i]:
			result.append(i)
	return result

def factor(N):
	factors = []
	i = 1
	while i * i <= N:
		if N % i == 0:
			factors.append(i)
			if i != N // i:
				factors.append(N // i)
		i += 1
	return sorted(factors)

def reduceB(b):
	mod = 0
	for i in range(0, len(b)):
		mod = (mod * 10 + ord(b[i])) % 1000000007
	return mod

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	(n, m) = get_ints_in_variables()
	arr = get_ints_in_list()
	posOne = 0
	negOne = 0
	for i in range(0, n):
		if arr[i] == 1:
			posOne += 1
		else:
			negOne += 1
	for _ in range(0, m):
		(l, r) = get_ints_in_variables()
		if l == r:
			print(0)
		elif (r - l + 1) % 2 != 0:
			print(0)
		else:
			diff = r - l + 1
			if posOne >= int(diff / 2) and negOne >= int(diff / 2):
				print(1)
			else:
				print(0)
main()


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')
	elif k <= vmin:
		sys.stdout.write('1\n')
	else:
		sys.stdout.write('0\n')


from sys import stdin
(n, m) = map(int, stdin.readline().strip().split())
arr = list(map(int, stdin.readline().strip().split()))
(a, b) = (arr.count(-1), arr.count(1))
for i in range(m):
	(l, r) = map(int, stdin.readline().strip().split())
	d = r - l + 1
	if d % 2 == 0:
		print(1 if min(a, b) >= d // 2 else 0)
	else:
		print(0)


from sys import stdin

def eugeny_and_array(n_int: int, m_int: int, array_list: list, queries_list: list) -> None:
	one_count = array_list.count(1)
	minus_one_count = len(array_list) - one_count
	for query in queries_list:
		count = query[1] - query[0] + 1
		(quotient, remainder) = divmod(count, 2)
		if remainder == 1:
			print(0)
		elif quotient <= one_count and quotient <= minus_one_count:
			print(1)
		else:
			print(0)
(n, m) = list(map(int, stdin.readline().split()))
array = list(map(int, stdin.readline().split()))
one_count = array.count(1)
minus_one_count = len(array) - one_count
lines = stdin.readlines()
for line in lines:
	(l, r) = list(map(int, line.split()))
	count = r - l + 1
	(quotient, remainder) = divmod(count, 2)
	if remainder == 1:
		print(0)
	elif quotient <= one_count and quotient <= minus_one_count:
		print(1)
	else:
		print(0)


(n, m) = 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) = map(int, input().split())
	length = right - left + 1
	if length % 2 or length // 2 > c:
		s += '0\n'
	else:
		s += '1\n'
print(s)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
positives = a.count(1)
negatives = a.count(-1)
mn = min(positives, negatives)
output = list()
for _ in range(m):
	(l, r) = map(int, input().split())
	if (r - l + 1) % 2 == 0 and (r - l + 1) / 2 <= mn:
		output.append('1')
	else:
		output.append('0')
print('\n'.join(output))


import sys
from math import *
input = sys.stdin.readline
RI = lambda : [int(x) for x in sys.stdin.readline().strip().split()]
rw = lambda : input().strip().split()
ls = lambda : list(input().strip())
from collections import defaultdict as df
import heapq
infinite = float('inf')
(n, m) = RI()
l = RI()
neg = 0
for i in l:
	if i == -1:
		neg += 1
pos = n - neg
for i in range(m):
	(a, b) = RI()
	t = b - a + 1
	if t % 2 == 0 and t // 2 <= neg and (t // 2 <= pos):
		print(1)
	else:
		print(0)


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


(n, m) = 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) = map(int, input().split())
	q = r - l + 1
	res[i] = '1' if q % 2 == 0 and q <= less else '0'
print('\n'.join(res))


import sys
inf = float('inf')

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, m) = get_ints()
Arr = get_array()
mydict = {1: 0, -1: 0}
for i in Arr:
	mydict[i] = mydict.get(i, 0) + 1
for i in range(m):
	(l, r) = get_ints()
	elements = r - l + 1
	if elements & 1:
		print(0)
	elif mydict[1] >= elements // 2 and mydict[-1] >= elements // 2:
		print(1)
	else:
		print(0)


(n, x) = map(int, input().split())
a = list(map(int, input().split()))
d = {1: 0}
for i in a:
	if i == 1:
		d[i] += 1
o = min(d[1], n - d[1])
k = []
for i in range(x):
	(l, r) = map(int, input().split())
	k.append(int(l + r + 1 & 1 == 0 and o >= (r - l + 1) // 2))
print(*k)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
count1 = l.count(1)
countneg1 = min(count1, n - count1)
res = ''
for i in range(m):
	(low, r) = map(int, input().split())
	rem = (r - low + 1) % 2
	t = (r - low + 1) // 2
	if rem == 0 and t <= countneg1:
		res += '1\n'
	else:
		res += '0\n'
print(res)


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


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
c1 = 0
c2 = 0
for i in range(n):
	if arr[i] == 1:
		c1 = c1 + 1
	else:
		c2 = c2 + 1
ans = ''
for i in range(m):
	(a, b) = map(int, input().split())
	diff = b - a + 1
	if diff % 2 == 0 and diff // 2 <= c2 and (diff // 2 <= c1):
		ans = ans + '1\n'
	else:
		ans = ans + '0\n'
print(ans)


(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))


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


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase
from fractions import *

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
(n, q) = value()
a = array()
ma = 2 * min(a.count(1), a.count(-1))
for i in range(q):
	(l, r) = value()
	tot = r - l + 1
	if tot % 2 == 0 and tot <= ma:
		print(1)
	else:
		print(0)


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


(a, b) = map(int, input().split())
z = list(map(int, input().split()))
(r, t) = (0, 0)
for i in z:
	if i > 0:
		r += 1
	else:
		t += 1
s = ''
for i in range(b):
	(q, w) = map(int, input().split())
	if (w - q + 1) % 2 == 0 and (w - q + 1) // 2 <= r and ((w - q + 1) // 2 <= t):
		s += '1\n'
	else:
		s += '0\n'
print(s)


I = lambda : map(int, input().split())
(n, m) = I()
x = sum((x > 0 for x in I()))
x = min(x, n - x)
o = []
while m:
	(l, r) = I()
	o += [[0, 1][(r - l) % 2 and (r - l + 1) // 2 <= x]]
	m -= 1
print(*o)


(n, m) = map(int, input().split())
l = input().split()
u1 = l.count('-1')
u2 = min(u1, n - u1)
r = []
for i in range(m):
	(a, b) = map(int, input().split())
	rr = b - a + 1
	if rr % 2 == 0 and rr <= 2 * u2:
		r.append(1)
	else:
		r.append(0)
for i in range(len(r)):
	print(r[i])


(N, M) = map(int, input().split())
A = input().split()
count_one = A.count('1')
solution = []
queries = []
for i in range(M):
	(Li, Ri) = 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) = map(int, input().split())
list1 = list(map(int, input().split()))
list1.sort()
neg = list1.count(-1)
pos = n - neg
ans = ''
x = min(neg, pos)
for i in range(m):
	(l, r) = map(int, input().split())
	y = r - l + 1
	if y % 2 == 0 and y <= x * 2:
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


temp = input().split(' ')
n = int(temp[0])
m = int(temp[1])
b = input()
cno = len(b) - (n * 2 - 1)
co = n - cno
outstr = ''
for i in range(m):
	temp = input().split(' ')
	l = int(temp[0])
	r = int(temp[1])
	d = r - l
	if d % 2 != 0 and cno >= d / 2 and (co >= d / 2):
		outstr += '1\n'
	else:
		outstr += '0\n'
print(outstr)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
readint = lambda : int(sys.stdin.readline().rstrip('\r\n'))
readints = lambda : map(int, sys.stdin.readline().rstrip('\r\n').split())
readstr = lambda : sys.stdin.readline().rstrip('\r\n')
readstrs = lambda : map(str, sys.stdin.readline().rstrip('\r\n').split())
readarri = lambda : [int(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]
readarrs = lambda : [str(_) for _ in sys.stdin.readline().rstrip('\r\n').split()]

def solve():
	(n, k) = readints()
	(on, op) = (0, 0)
	arr = readarri()
	for i in arr:
		on += i == -1
		op += i == 1
	for i in range(k):
		(l, r) = readints()
		check = r - l + 1
		if check & 1:
			print(0)
			continue
		if op >= check >> 1 and on >= check >> 1:
			print(1)
		else:
			print(0)

def main():
	t = 1
	for _ in range(t):
		solve()
main()


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, q) = map(int, input().split())
l = list(map(int, input().split()))
s = 0
t = 0
d = {1: 0, -1: 0}
ans = ''
for i in range(n):
	d[l[i]] = d[l[i]] + 1
for i in range(q):
	(l1, r1) = map(int, input().split())
	if (-l1 + r1) % 2 == 0:
		ans += '0\n'
	elif d[1] >= (r1 - l1 + 1) // 2 and d[-1] >= (r1 - l1 + 1) // 2:
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


(n, m) = input().split()
(n, m) = (int(n), int(m))
l1 = [int(i) for i in input().split()]
ans = ''
p = l1.count(1)
for _ in range(m):
	(l, r) = input().split()
	(l, r) = (int(l), int(r))
	x = abs(l - r) + 1
	if (l + r) % 2 != 0 and x // 2 <= min(p, n - p):
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


import sys
import math
import itertools
import collections

def getdict(n):
	d = {}
	if type(n) is list or type(n) is str:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return '\n'.join(map(str, arr))

def revn(n):
	return int(str(n)[::-1])

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True
(n, m) = mi()
a = li()
nc = a.count(-1)
pc = n - nc
mc = min(nc, pc)
ans = [0] * m
for i in range(m):
	(l, r) = mi()
	if (r - l) % 2 == 0 or (r - l + 1) // 2 > mc:
		ans[i] = 0
	else:
		ans[i] = 1
print(wr(ans))


I = lambda : map(int, input().split())
(_, m) = I()
A = list(I())
(x, y) = (2 * A.count(-1), 2 * A.count(1))
B = []
for _ in range(m):
	(L, R) = I()
	k = R - L + 1
	B.append(1 - (k % 2 or x < k or y < k))
print(*B)


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


(n, m) = map(int, input().split())
ini = map(int, input().split())
aux = 0
res = list()
for i in ini:
	if i > 0:
		aux += i
for i in range(m):
	(a1, a2) = map(int, input().split())
	if (a2 - a1 + 1) // 2 <= min(aux, n - aux) and (a2 - a1) % 2 != 0:
		res += [[0, 1][1]]
	else:
		res += [[0, 1][0]]
for i in res:
	print(i)


(a, q) = map(int, input().split())
x = [int(x) for x in input().split()]
m = x.count(-1)
re = min(m, a - m)
ans = ''
for i in range(q):
	(l, r) = map(int, input().split())
	t = r - l + 1
	if t % 2 == 0 and t // 2 <= re:
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
(p, ne) = (0, 0)
for i in range(n):
	if a[i] == 1:
		p += 1
	else:
		ne += 1
ans = ''
for j in range(m):
	(l, r) = map(int, input().split())
	if (r - l + 1) % 2 == 0 and (r - l + 1) // 2 <= p and ((r - l + 1) // 2 <= ne):
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


(n, m) = [int(x) for x in input().split(' ')]
downs = input().count('-')
ups = n - downs
min = min(ups, downs)
answer = ''
for q in range(m):
	(l, r) = [int(x) for x in input().split(' ')]
	if (r - l + 1) % 2 == 0 and min >= (r - l + 1) // 2:
		answer += '1\n'
	else:
		answer += '0\n'
print(answer)


inp = input().split()
(n, m) = (int(inp[0]), int(inp[1]))
vet = input().split()
occur = min(vet.count('-1'), n - vet.count('-1'))
res = []
while m > 0:
	line = input().split()
	(first, second) = (int(line[0]), int(line[1]))
	aux = (second - first) % 2
	aux2 = (second - first + 1) // 2
	if occur < aux2 or aux != 1:
		res.append('0')
	else:
		res.append('1')
	m -= 1
print('\n'.join(res))


import sys
(n, m) = [int(x) for x in sys.stdin.readline().strip().split()]
l = [int(x) for x in sys.stdin.readline().strip().split()]
(x, y) = (0, 0)
for i in range(n):
	if l[i] == 1:
		x = x + 1
y = n - x
for u in range(m):
	(a, b) = [int(x) for x in sys.stdin.readline().strip().split()]
	s = b - a + 1
	if s % 2 == 0 and s // 2 <= y and (s // 2 <= x):
		print(1)
	else:
		print(0)


import sys

def main():
	(n, m) = 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) = map(int, sys.stdin.readline().split(' '))
		count = r - l + 1
		if count % 2 != 0:
			sys.stdout.write('0\n')
		elif ones >= count // 2 and negs >= count // 2:
			sys.stdout.write('1\n')
		else:
			sys.stdout.write('0\n')
main()


import sys
zr = 48

def intt(s):
	res = 0
	idx = 0
	l = len(s)
	while idx < l:
		if ord(s[idx]) < 48:
			return res
		res = (res << 3) + (res << 1)
		res += ord(s[idx]) - zr
		idx += 1
	return res
(nums, queries) = map(intt, input().split())
neg_1 = sys.stdin.readline().count('-')
pos_1 = nums - neg_1
for _ in range(queries):
	s = sys.stdin.readline()
	fd = False
	(l, r) = ('', '')
	for i in s:
		if i == ' ':
			fd = True
			continue
		if fd:
			r += i
		else:
			l += i
	number_in_range = intt(r) + 1 - intt(l)
	if number_in_range & 1:
		sys.stdout.write('0\n')
	else:
		actual_count = number_in_range / 2
		if actual_count <= pos_1 and actual_count <= neg_1:
			sys.stdout.write('1\n')
		else:
			sys.stdout.write('0\n')


I = lambda : map(int, input().split())
(_, m) = I()
s = list(I())
x = 2 * s.count(-1)
y = 2 * s.count(1)
b = []
for _ in range(m):
	(l, r) = map(int, input().split())
	k = r - l + 1
	b.append(1 - (k % 2 or x < k or y < k))
print(*b)


(n, m) = map(int, input().split())
l1 = list(map(int, input().split()))
x = l1.count(-1)
x = min(x, n - x)
x = 2 * x
ans = []
for i in range(m):
	(l, r) = map(int, input().split())
	if (r - l + 1) % 2 == 1:
		ans.append(0)
	elif (r - l + 1) % 2 == 0 and r - l + 1 <= x:
		ans.append(1)
	else:
		ans.append(0)
for item in ans:
	print(item)


T_ON = 0
DEBUG_ON = 1
MOD = 998244353

def solve():
	(n, m) = read_ints()
	A = read_ints()
	G = Counter(A)
	for i in range(m):
		(L, R) = read_ints()
		x = R - L + 1
		if x % 2:
			print(0)
		elif G[-1] >= x // 2 and G[1] >= x // 2:
			print(1)
		else:
			print(0)

def main():
	T = read_int() if T_ON else 1
	for i in range(T):
		solve()

def debug(*xargs):
	if DEBUG_ON:
		print(*xargs)
from collections import *
import math
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int():
	return int(input())

def read_ints():
	return list(map(int, input().split()))

def print_nums(nums):
	print(' '.join(map(str, nums)))

def YES():
	print('YES')

def Yes():
	print('Yes')

def NO():
	print('NO')

def No():
	print('No')

def First():
	print('First')

def Second():
	print('Second')

def fib(n):
	(a, b) = (0, 1)
	for _ in range(n):
		(a, b) = (b, a + b)
	return a

def fib_ns(n):
	assert n >= 1
	f = [0 for _ in range(n + 1)]
	f[0] = 0
	f[1] = 1
	for i in range(2, n + 1):
		f[i] = f[i - 1] + f[i - 2]
	return f

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def xgcd(a, b):
	(x0, x1, y0, y1) = (0, 1, 1, 0)
	while a != 0:
		((q, a), b) = (divmod(b, a), a)
		(y0, y1) = (y1, y0 - q * y1)
		(x0, x1) = (x1, x0 - q * x1)
	return (b, x0, y0)

def lcm(a, b):
	d = gcd(a, b)
	return a * b // d

def is_even(x):
	return x % 2 == 0

def is_odd(x):
	return x % 2 == 1

def modinv(a, m):
	(g, x, _) = xgcd(a, m)
	if g != 1:
		raise Exception('gcd(a, m) != 1')
	return x % m

def mod_add(x, y):
	x += y
	while x >= MOD:
		x -= MOD
	while x < 0:
		x += MOD
	return x

def mod_mul(x, y):
	return x * y % MOD

def mod_pow(x, y):
	if y == 0:
		return 1
	if y % 2:
		return mod_mul(x, mod_pow(x, y - 1))
	p = mod_pow(x, y // 2)
	return mod_mul(p, p)

def mod_inv(y):
	return mod_pow(y, MOD - 2)

def mod_div(x, y):
	return mod_mul(x, mod_inv(y))

def is_prime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i:
			return False
	return True

def gen_primes(n):
	P = [True for _ in range(n + 1)]
	P[0] = P[1] = False
	for i in range(int(n ** 0.5) + 1):
		if P[i]:
			for j in range(2 * i, n + 1, i):
				P[j] = False
	return P
main()


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
o1 = a.count(1)
o0 = a.count(-1)
s = ''
for i in range(m):
	(l, r) = map(int, input().split())
	u = r - l + 1
	uu = u // 2
	if u % 2 == 0 and o1 >= uu and (o0 >= uu):
		s = s + '1'
	else:
		s = s + '0'
for i in s:
	print(i)


import sys
import itertools
import math
import collections
from collections import Counter

def pow(x, y, mod):
	r = 1
	x = x % mod
	while y > 0:
		if y & 1:
			r = r * x % mod
		y = y >> 1
		x = x * x % mod
	return r

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = prime[1] = False
	r = [p for p in range(n + 1) if prime[p]]
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def prr(a, sep=' '):
	print(sep.join(map(str, a)))

def dd():
	return collections.defaultdict(int)
(n, m) = mi()
d = li()
p = d.count(1)
x = min(p, n - p)
res = ''
for _ in range(m):
	(l, r) = mi()
	t = r - l + 1
	res += '0\n' if t % 2 or t // 2 > x else '1\n'
print(res)


(n, m) = map(int, input().split())
lst = list(map(int, input().split()))
(coutone, coutmone) = (0, 0)
for (i, x) in enumerate(lst):
	if x == 1:
		coutone += 1
	else:
		coutmone += 1
from sys import stdin
res = ''
for i in range(m):
	(l, r) = map(int, stdin.readline().split())
	(x, y) = ((r - l + 1) // 2, (r - l + 1) % 2)
	if y == 0:
		if coutone >= x and coutmone >= x:
			res += '1\n'
		else:
			res += '0\n'
	else:
		res += '0\n'
print(res[:m * 2 - 1])


import sys
(n, m) = map(int, sys.stdin.readline().split())
neg = sum((x < 0 for x in map(int, sys.stdin.readline().split())))
d = min(neg, n - neg) * 2
for i in range(m):
	(l, r) = map(int, sys.stdin.readline().split())
	print(int(0 < r - l < d and r - l & 1))


from collections import Counter
(num, cases) = map(int, input().split())
arr = list(map(int, input().split()))
count = Counter(arr)
minus = count[-1]
plus = count[1]
mn = min(plus, minus)
ans = []
mat = []
while cases:
	cases -= 1
	(a, b) = map(int, input().split())
	mat.append((a, b))
for (a, b) in mat:
	if (b - a + 1) % 2 != 0:
		print(0)
	elif (b - a + 1) // 2 <= mn:
		print(1)
	else:
		print(0)


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
mat = []
for i in range(m):
	mat.append(list(map(int, input().split())))
l1 = arr.count(1)
l2 = arr.count(-1)
for i in mat:
	len = i[1] - i[0] + 1
	if len % 2 == 0:
		if l1 >= len // 2 and l2 >= len // 2:
			print(1)
		else:
			print(0)
	else:
		print(0)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
p = ''
s = sum(a)
if s > 0:
	d = n - s
	neg = pos = d // 2
	pos += s
else:
	d = n + s
	neg = pos = d // 2
	neg -= s
for i in range(m):
	(l, r) = map(int, input().split())
	d = r - l + 1
	r = d % 2
	if r:
		p += '0\n'
	elif d // 2 <= neg and d // 2 <= pos:
		p += '1\n'
	else:
		p += '0\n'
print(p)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
k = a.count(1)
l = a.count(-1)
ans = ''
for i in range(m):
	(x, y) = map(int, input().split())
	if (y - x + 1) // 2 <= k and (y - x + 1) // 2 <= l and ((y - x + 1) % 2 == 0):
		ans += '1\n'
	else:
		ans += '0\n'
print(ans)


import sys
input = sys.stdin.buffer.readline
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
count1 = 0
for x in a:
	if x == 1:
		count1 += 1
count0 = n - count1
while m:
	m -= 1
	(l, r) = map(int, input().split())
	if (r - l + 1) % 2 == 0:
		if (r - l + 1) // 2 <= min(count0, count1):
			print('1')
		else:
			print('0')
	else:
		print('0')


I = lambda : map(int, input().split())
(_, m) = I()
s = list(I())
x = 2 * s.count(-1)
y = 2 * s.count(1)
b = []
for _ in range(m):
	(l, r) = map(int, input().split())
	k = r - l + 1
	if k % 2 == 0:
		if y >= k and x >= k:
			b.append(1)
		else:
			b.append(0)
	else:
		b.append(0)
print(*b)


import os
import sys
from io import BytesIO, IOBase
import math
from decimal import Decimal
from decimal import *
from collections import defaultdict, deque
import heapq
from decimal import Decimal
getcontext().prec = 25
abcd = 'abcdefghijklmnopqrstuvwxyz'
MOD = 1000000007
BUFSIZE = 8192
from bisect import bisect_left, bisect_right

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split(' '))
l = list(map(int, input().split(' ')))
m = l.count(-1)
mm = l.count(1)
for i in range(k):
	(y, x) = map(int, input().split(' '))
	if (x - y + 1) % 2:
		print('0')
	elif m >= (x - y + 1) // 2 and mm >= (x - y + 1) // 2:
		print(1)
	else:
		print(0)