题目描述

Eugeny 有一个数组 $a = a_1, a_2, ..., a_n$，包含 $n$ 个整数。每个整数 $a_i$ 只可能是 $-1$ 或 $1$。他还有 $m$ 个询问：

• 第 $i$ 个询问用一对整数 $l_i$, $r_i$（$1 \leq l_i \leq r_i \leq n$）表示。
• 对于每个询问，如果数组 $a$ 可以重新排列，使得区间 $a_{l_i} + a_{l_i+1} + \cdots + a_{r_i} = 0$，则回答 $1$，否则回答 $0$。

请你帮助 Eugeny，回答他的所有询问。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$）。
第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$a_i = -1$ 或 $a_i = 1$）。
接下来的 $m$ 行，每行包含两个整数 $l_i, r_i$（$1 \leq l_i \leq r_i \leq n$），表示第 $i$ 个询问。

输出格式

输出 $m$ 个整数，按照输入顺序，每个整数为 Eugeny 对应询问的回答。

说明/提示

由 ChatGPT 5 翻译

样例

2 3
1 -1
1 1
1 2
2 2

0
1
0

5 5
-1 1 1 1 -1
1 1
2 3
3 5
2 5
1 5

0
1
0
1
0