Eugeny has array a = a1, a2, ..., an, consisting of n integers. Each integer ai equals to -1, or to 1. Also, he has m queries:
- Query number i is given as a pair of integers li, ri (1 ≤ li ≤ ri ≤ n).
- The response to the query will be integer 1, if the elements of array a can be rearranged so as the sum ali + ali + 1 + ... + ari = 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·105). The second line contains n integers a1, a2, ..., an (ai = -1, 1). Next m lines contain Eugene's queries. The i-th line contains integers li, ri (1 ≤ li ≤ ri ≤ 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
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
int n,m;
int num[200005];
cin>>n>>m;
int sum1=0,sum2=0;
for(int t=0; t<n; t++) {
scanf("%d",&num[t]);
if(num[t]==-1) {
sum1++;
} else {
sum2++;
}
}
int l,r;
for(int t=0; t<m; t++) {
scanf("%d%d",&l,&r);
if((r-l)%2==0)
printf("0
");
else if((r-l)%2!=0) {
if((r-l+1)/2<=sum1&&(r-l+1)/2<=sum2)
printf("1
");
else
printf("0
");
}
}
return 0;
}