Eugeny and Array（水题，注意题目描述即可）

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

Output

Input

5 5

-1 1 1 1 -1

1 1

2 3

3 5

2 5

1 5

Output

代码

#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\n");

		else if((r-l)%2!=0) {

			if((r-l+1)/2<=sum1&&(r-l+1)/2<=sum2)

				printf("1\n");

			else

				printf("0\n");

		}

	}

	return 0;

}

巴特西

Eugeny and Array（水题，注意题目描述即可）

最新文章

热门文章