### 问题描述 $01$ 王国生活着两种数字，一种是 $0$ ，一种是 $1$ ，因为 $0$ 更喜欢自己胖胖的样子，而 $1$ 更喜欢自己瘦瘦的样子，两种数字审美不同导致它们经常起争执。 终于有一天，它们开战啦！ 战斗场面十分的混乱，两边数字都混在了一起。给一个数组描述当前的场面，比如 $“0 0 1 0 1 1 1 0”$ ，而我们知道，人多力量大，如果某一段区间内，$“0 0”$ 子串的数量多于 $“1 1”$ 子串，那么 $0$ 就会获胜，反之 $1$ 会获胜。比如在上面的数组中第一个数到第四个数之间，$“0 0”$ 子串的数量为 $1$ ，$“1 1”$ 子串的数量为 $0$ ，所以 $0$ 获胜了；第一个数到第七个数之间，$“0 0”$ 子串的数量为 $1$ ，$“1 1”$ 子串的数量为 $2$ ，所以 $1$ 获胜了。 现在给你一个长度为 $n$ 的，只由 $0$ 和 $1$ 组成的数组，然后对你进行 $m$ 次询问，每次给出一个区间 $[l，r]$ ，问这个区间里谁会赢，且赢得那一方有多少个 $“x x”$ 子串。 ### 输入格式 第一行包含 $2$ 个正整数 $n$ 和 $m$ ，表示数组的长度和询问的次数。 第二行包含 $n$ 个正整数 $a_i$，$a_i$ 表示第 $i$ 个位置上的数字是 $a_i$ 。 接下来 $m$ 行，每行包含 $2$ 个正整数 $l$ 和 $r$ ,表示当前询问的区间。 ### 输出格式 对于每一行询问，输出 $2$ 个整数。 第 $1$ 个整数表示赢的是哪一个数字，如果是 $0$ 赢就输出 $0$ ，如果是 $1$ 赢就输出 $1$ ，如果打平，就输出 $-1$ 。 第 $2$ 个整数表示赢的那一方在当前询问的区间里，有几个 $"x x"$ 子串，如果平手，则输出任意一个数字的 “x x” 子串数量即可。 ### 样例输入 ```text 8 3 0 0 1 0 1 1 1 0 1 3 1 7 2 3 ``` ### 样例输出 ```text 0 1 1 2 -1 0 ``` ### 说明 **样例说明** 第一次询问 $[1，3]$ ,有 $1$ 个 $“0 0”$ 子串，有 $0$ 个 $“1 1”$ 子串，所以 $0$ 赢了。 第二次询问 $[1，7]$ ,有 $1$ 个 $“0 0”$ 子串，有 $2$ 个 $“1 1”$ 子串，所以 $1$ 赢了。 第三次询问 $[2，3]$ ,有 $0$ 个 $“0 0”$ 子串，有 $0$ 个 $“1 1”$ 子串，两边打平。 **提示** 注意，因为本题输入输出数据较大，所以要用快一些的输入输出方式，比如 $scanf$ 和 $printf$ 。如果想使用 $cin$ 和 $cout$ ，需要关闭流同步。 以及换行不能使用 $endl$ 作为换行符，要用 $"\setminus n"$ 。 **评测数据规模** 对于所有评测数据，$1\leq n,m \leq 1\times 10^6$ ，$0\leq a_i \leq 1$ ，$1\leq l,r \leq n$ 。