Description

You are given an $n \times m$ 01 matrix. In each operation, you can flip the value at one position and the values directly above, left, and right of it. If the original value is $0$, it becomes $1$ after flipping; otherwise it becomes $0$.

For example, the matrix below becomes the following after flipping the position marked by brackets:

$$\begin{bmatrix}0&1&0&1&1\\1&0&[0]&1&0\\0&0&0&0&1\end{bmatrix}\rightarrow \begin{bmatrix}0&1&1&1&1\\1&1&1&0&0\\0&0&0&0&1\end{bmatrix}$$

In particular, if the operation position is on the boundary, only the part that does not go out of bounds will be flipped.

Now you are given $q$ queries. Each query provides an interval $[l, r]$ and a constant $k$. For the 01 submatrix consisting of rows with indices in $[l, r]$, consider all ways to make it all $0$ by choosing some positions to perform exactly one operation on each chosen position. In those ways, output how many times row $k$ is operated on.

In particular, if there is no way, or there are multiple ways to choose operation positions, output $-1$.

Queries are independent of each other.

Input Format

The first line contains three integers $n, m, q$.

The next $n$ lines each contain $m$ characters, describing the 01 matrix.

The next $q$ lines each contain three integers $l, r, k$, describing a query.

Output Format

Output $q$ lines. Each line contains one integer, the answer to the corresponding query.

10 4 2
1010
0110
0101
0000
1011
0111
1110
1011
0001
1100
1 10 6
2 5 3

2
2

Hint

• Subtask 1 (10 pts): $n, m \leq 3, q \leq 10$.
• Subtask 2 (20 pts): $n, m, q \leq 10$.
• Subtask 3 (20 pts): $n, q \leq 50, m \leq 10$.
• Subtask 4 (20 pts): $n, q \leq 10^4, m \leq 10$.
• Subtask 5 (30 pts): No special constraints.

For $100\%$ of the testdata, $1 \leq n \leq 5 \times 10^4$, $1 \leq m \leq 50$, $1 \leq q \leq 5 \times 10^5$, $1 \leq l \leq k \leq r \leq n$.

idea: Sol1, solution: Sol1 & ethan_zhou, code: Sol1, data: Sol1

---

"Talisman..."

"An angel won't give up its wings unless
it has finished the last dance, right?"

Translated by ChatGPT 5