题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，其中 $a_i \in \{0,1\}$。

现在有 $q$ 次询问，每次询问给定三个整数 $l, r, k$。你需要更改序列在区间 $[l, r]$ 内某些位置上的数值（只能改为 $0$ 或 $1$），使得满足以下等式：

也就是说，要让 $a_l \sim a_r$ 这段区间的元素之和，恰好等于它们的乘积再加上 $k$。

请针对每次询问，求出最少的修改次数。如果无论如何修改都无法满足条件，请输出 -1。

请注意：每次询问中的更改只是假设，不会对后续的询问产生实际影响。

公式中的 $\sum_{i=l}^r a_i$ 是求和符号，表示对序列中从下标 $l$ 到 $r$ 的所有元素进行相加，即 $a_l + a_{l+1} + \dots + a_r$。

公式中的 $\prod_{i=l}^r a_i$ 是求积（连乘）符号，表示对序列中从下标 $l$ 到 $r$ 的所有元素进行相乘，即 $a_l \times a_{l+1} \times \dots \times a_r$。

输入格式

第一行包含两个正整数 $n, q$ —— 分别表示序列的长度和询问的次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示序列 $a$ 的元素。

接下来 $q$ 行，每行包含三个整数 $l, r, k$，表示一次询问。

输出格式

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

样例输入 1

5 4
0 0 1 0 1
1 3 2
2 4 0
3 5 2
1 1 1

样例输出 1

1
1
0 
-1

样例输入 2

8 3
1 1 1 1 1 1 1 1
2 6 2
5 8 2
1 8 7

样例输出 2

3
2
0

说明

样例解释

对于样例 $1$，序列为 $a=\{0,0,1,0,1\}$：

• 第一个询问 $[1, 3]$，目标 $k=2$。只需将 $a_1$ 或 $a_2$ 改为 $1$。修改后区间元素为 $\{1,0,1\}$ 或 $\{0,1,1\}$，此时和为 $2$，乘积为 $0$，$2 = 0 + 2$ 成立。最少修改 $1$ 次。
• 第二个询问 $[2, 4]$，目标 $k=0$。只需将 $a_3$ 改为 $0$。修改后区间元素为 $\{0,0,0\}$，此时和为 $0$，乘积为 $0$，$0 = 0 + 0$ 成立。最少修改 $1$ 次。
• 第三个询问 $[3, 5]$，目标 $k=2$。不需进行更改，原区间元素为 $\{1,0,1\}$，和为 $2$，乘积为 $0$，$2 = 0 + 2$ 成立。最少修改 $0$ 次。
• 第四个询问 $[1, 1]$，目标 $k=1$。因为只有一个数，所以它的和与积永远相等（无论是 $0$ 还是 $1$），不可能满足“和 = 积 $+ 1$”，所以无解，输出 -1。

数据范围

对于所有测试点，保证:

• $1 \le n, q \le 10^6$。
• $0 \le k \le 10^6$。
• $1 \le l \le r \le n$。
• 保证 $a_i \in \{0, 1\}$。
• 保证所有的输入数值均为整数。