Eugeny 有数组 a = a1, a2, ..., an,由 n 个整数组成。每个整数 ai 等于 -1 或 1。此外,他有 m 个查询:
- 查询号 i 给出为一对整数 li, ri (1 ≤ li ≤ ri ≤ n)。
- 如果数组 a 的元素可以重新排列,使得总和 ali + ali + 1 + ... + ari = 0,则对查询的响应将为整数 1,否则对查询的响应将为整数 0。
帮助尤金尼,回答他所有的疑问。
输入
第一行包含整数 n 和 m (1 ≤ n, m ≤ 2·105)。第二行包含n个整数a1, a2, ..., an (ai = -1, 1)。接下来的 m 行包含尤金的查询。第 i 行包含整数 li, ri (1 ≤ li ≤ ri ≤ n)。
输出
打印 m 个整数 — 按照输入中出现的顺序对 Eugene 查询的响应。
示例
输入 #1
2 3 1 -1 1 1 1 2 2 2
输出 #1
0 1 0
输入 #2
5 5 -1 1 1 1 -1 1 1 2 3 3 5 2 5 1 5
输出 #2
0 1 0 1 0