CF302A.Eugeny and Array

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.

尤金有一个由 $n$ 个整数组成的数组 $a = a_1, a_2, \dots, a_n$。每个整数 $a_i$ 的值为 $-1$ 或 $1$。此外，他还有 $m$ 个查询：

• 第 $i$ 个查询以一对整数 $l_i, r_i$ 给出（满足 $1 \leq l_i \leq r_i \leq n$）；
• 对该查询的回答为整数 $1$，当且仅当数组 $a$ 的元素可以被重新排列，使得子段和 $a_{l_i} + a_{l_i+1} + \dots + a_{r_i} = 0$；否则回答为整数 $0$。

请帮助尤金回答所有查询。

The first line contains integers n and m (1 ≤ n, m ≤ 2·105). 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).

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2\cdot10^5$）。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（其中每个 $a_i = -1$ 或 $1$）。接下来的 $m$ 行是尤金的查询。第 $i$ 行包含两个整数 $l_i$、$r_i$（$1 \le l_i \le r_i \le n$）。

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

输出 m 个整数——即尤金查询的响应结果，按输入中出现的顺序输出。