Matrix Toggle Puzzle

Given an \( n\times m \) binary matrix and an operation that toggles a cell along with its top, left, and right neighbors (if they exist), you are to answer \(q\) independent queries. In each query, you are given an interval \([l, r]\) (representing a contiguous block of rows) and an integer \( k \) (with \(l\le k\le r\)). Consider the submatrix formed by rows \(l\) to \(r\) (1-indexed) of the original matrix. Each operation is defined as follows:

When you operate on a cell \((i,j)\) (where indices refer to the submatrix), the values at \((i,j)\), at \((i, j-1)\), at \((i, j+1)\), and at \((i+1,j)\) are flipped (i.e. changed from \(0\) to \(1\) or from \(1\) to \(0\)). Note that if any of these positions lies outside the submatrix boundaries, it is ignored.

We can view the effect of the operations as a system of linear equations over \( \mathbb{F}_2 \) (i.e. modulo 2) where for each cell in the submatrix the sum \[ op(i,j) + op(i,j-1) + op(i,j+1) + op(i+1,j) \equiv initial(i,j) \pmod{2}, \] with \(op(i,j)\) equal to \(1\) if an operation is performed at that cell and \(0\) otherwise. (Here, an operation at \((i+1,j)\) also affects cell \((i,j)\) because it toggles its above neighbor.)

Your task for each query is to decide whether there exists a unique set of operations (each position may be chosen at most once) that turns the submatrix into an all zero matrix. If there is no solution or if there are multiple solutions, output \( -1 \). Otherwise, output the number of operations (i.e. the number of chosen cells) in the \( k \)th row of the submatrix.

Note: The rows and columns of the original matrix are 1-indexed. The queries are independent.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of rows and columns of the matrix.

The next \(n\) lines each contain \(m\) binary digits (0 or 1), which represent the matrix.

The following line contains an integer \(q\), the number of queries.

Each of the next \(q\) lines contains three integers \(l\), \(r\), and \( k \) (all 1-indexed) describing a query.

outputFormat

For each query, output one integer: the number of operations in the \( k \)th row (of the submatrix formed by rows \(l\) to \(r\)) in the unique solution that turns the submatrix into an all zero matrix, or \( -1 \) if there is no solution or if there are multiple solutions.

sample

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

3
-1
-1