Background

"Talisman, could you go out with Avalanche for a while instead of me?"

"I want to be alone tonight."

"My wife and daughter are dead.
Just confirmed..."

"I protected my country,
but I couldn't protect my family."

"What kind of ace
can't even protect his own family?"

"Monica...
and Jessica..."

"How could I let this happen！！"

"After this mission,
I will leave the air force."

"I've had enough.
I have no reason to keep flying."

......

"An unidentified object is flying at high speed
to the northeast."

"Is that a fighter jet? At a time like this?!"

"Unknown object confirmed on radar.
This isn't a fighter jet, it's way too fast!"

"The unknown object disappeared from radar.
Wait..."

"Some objects are flying in the same direction. I think this is..."

"I see them, these are missiles!"

"Ghost Eye,
we are under attack by cruise missiles!"

"All aircraft, intercept those cruise missiles!
Protect our city!"

......

"Checking intel...
Reinforcing stealth aircraft are approaching."

"These guys don't know when to give up, do they?"

'We're back for you, Emmeria!'

"What is wrong with these people? Do they really think not enough people have died yet?!"

$$_{{\frac{\large\text{ACE COMBAT }\Large6}{\tiny{\text{F i r e s\quad O f\quad L i b e r a t i o n}}}}}\\ \text{Mission 14} \\\Large\text{Gracemeria Patrol}\\\tiny -\textit{ City Lights }-$$

Problem 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