P11272 「Diligent-OI R1 B」DlgtArray

现给定一个长为 $n$ 的序列 $a_1\sim a_n$，其中 $a_i\in\{0,1\}$。 $q$ 次询问，每次给定 $l,r,k$，要你更改一些位置上的数值（只能改为 $0$ 或 $1$）使得 $\sum\limits_{i=l}^ra_i=k+\prod\limits_{i=l}^ra_i$。也就是说要让 $a_l\sim a_r$ 的和要恰好等于 $a_l\sim a_r$ 的乘积再加上 $k$。你需要求出最少的修改次数。如果无解，输出 $-1$。 **请注意每次的更改不会对后续询问产生影响。**

第一行输入 $n,q$。 接下来一行 $n$ 个整数 $a_1\sim a_n$。 接下来 $q$ 行，每行三个整数 $l,r,k$。

输出 $q$ 行，每行一个整数表示最少的修改次数。如果无解请输出 `-1`。

#### 样例 #1 解释 $a=\{0,0,1,0,1\}$。 第一个询问只需将 $a_1$ 或 $a_2$ 改为 $1$。此时和为 $2$，积为 $0$。 第二个询问只需将 $a_3$ 改为 $0$。此时和为 $0$，积为 $0$。 第三个询问不需进行更改，和为 $2$，积为 $0$。 第四个询问，因为只有一个数，所以和与积相等，所以不可能做到。 #### 数据范围 对于 $100\%$ 数据，$1\le n,q\le10^6$，$0\le k\le10^6$，$1\le l\le r\le n$，$a_i\in\{0,1\}$。 | Subtask 编号 | $n,q\le$ | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | :----------: | | $0$ | $10$ | 无 | $10$ | | $1$ | $10^3$ | A | $7$ | | $2$ | $10^3$ | BC | $7$ | | $3$ | $10^3$ | B | $13$ | | $4$ | $10^3$ | C | $13$ | | $5$ | $10^3$ | 无 | $20$ | | $6$ | $10^5$ | B | $9$ | | $7$ | $10^5$ | C | $9$ | | $8$ | $10^6$ | 无 | $12$ | 特殊性质 A：$k=n$。 特殊性质 B：$\forall 1\le i\le n,a_i=0$。 特殊性质 C：$k=0$。