Description

现给定一个长为 $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$。

请注意每次的更改不会对后续询问产生影响。

Input Format

第一行输入 $n,q$。

接下来一行 $n$ 个整数 $a_1\sim a_n$。

接下来 $q$ 行，每行三个整数 $l,r,k$。

Output Format

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

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

1
1
0 
-1

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

3
2
0

Hint

样例 #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\}$。

特殊性质 A：$k=n$。

特殊性质 B：$\forall 1\le i\le n,a_i=0$。

特殊性质 C：$k=0$。