Minimum Modifications to Satisfy Sum-Product Equation

Given a binary sequence (a_1, a_2, \dots, a_n) where (a_i \in {0,1}), you are to answer (q) queries. For each query, three integers (l, r, k) are given. You are allowed to modify some elements in the subarray (a_l, a_{l+1}, \dots, a_r) (each modification can only change an element to either 0 or 1) so that the following equation is satisfied:

[ \sum_{i=l}^{r} a_i = k + \prod_{i=l}^{r} a_i ]

Note that the product (\prod_{i=l}^{r} a_i) is 1 if all elements in the subarray are 1, and 0 otherwise. Thus there are two cases:

1. All Ones: In order for (\prod_{i=l}^{r} a_i = 1), the subarray must consist entirely of ones, and then (\sum_{i=l}^{r} a_i = r-l+1). The equation becomes (r-l+1 = k + 1), or (k = r-l). The cost here is the number of zeros in the subarray.

2. Not All Ones: Here (\prod_{i=l}^{r} a_i = 0). To satisfy the equation, we require (\sum_{i=l}^{r} a_i = k). In this case, the subarray must contain exactly (k) ones (and at least one zero, noting that (k \leq r-l)). The cost is the minimum number of modifications needed to achieve exactly (k) ones, which is (|\text{(current number of ones)} - k|).

Each query is independent; modifications made in one query do not affect subsequent queries. If it is impossible to achieve the required configuration, output (-1).

inputFormat

The first line contains two integers (n) and (q) representing the length of the sequence and the number of queries respectively.\nThe second line contains (n) integers (each 0 or 1) denoting the sequence (a_1, a_2, \dots, a_n).\nEach of the next (q) lines contains three integers (l, r, k) defining a query.

outputFormat

For each query, output a single line containing the minimum number of modifications needed to satisfy the equation (\sum_{i=l}^{r} a_i = k + \prod_{i=l}^{r} a_i). If no solution exists, output (-1).

sample

3 3
1 0 1
1 3 2
1 3 1
1 3 3

0
1
-1