Radical has an array consisting of n integers.Each integer a[i] equals to 1,or to -1.Also Radical asks you 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[R[i]] = 0,
otherwise the response to the query will be integer 0.

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].Next m lines
contain Radical's queries.The i-th line contains integers L[i],R[i](1<=L[i]<=R[i]<=n)

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