题目背景

「Talisman，一会你能不能和 Avalanche 一起出去而不是我？」

「我今晚想一个人静静。」

「我的妻女都死了。
　刚刚确认的……」

「我保护了我的国家，
　但我却守护不了我的家庭。」

「什么样的王牌
　连自己的家庭都保护不了？」

「Monica……
　还有 Jessica……」

「How could I let this happen！！」

「这个任务结束之后，
　我将离开空军。」

「我受够了。
　我没有继续飞行的理由了。」

……

「一个不明物体正在高速飞行
　在东北方。」

「这是战机？在这个时候？！」

「在雷达上确认未知物体，
　这不是战机，它的速度太快了！」

「未知物体在雷达上消失了。
　等一下……」

「一些物体在相同的方向上飞行。我认为这是……」

「我看到了，这些是导弹！」

「Ghost Eye，
　我们遭到巡航导弹袭击了！」

「全机，拦截那些巡航导弹！
　保护我们的城市！」

……

「资料检查……
　增援的隐形飞机正在接近。」

「这些人不懂得放弃吗？」

『我们为了你而回来了，Emmeria！』

「这些人到底是怎么了？还觉得死的人不够多吗？！」

$$_{{\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 }- $$

题目描述

给定一个 $n\times m$ 的 01 矩阵，每一次操作可以改变一个位置以及其上面、左边、右边的值。如果原值是 $0$，则改变之后变成 $1$；否则变成 $0$。

例如下面矩阵在改变中括号表明的位置之后的形态：

$$\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} $$

特别的，如果操作点在边界上，那么仅改变未超出边界的部分。

现给定 $q$ 组询问，每组询问一个区间 $[l,r]$ 和一个常数 $k$，请你对行号在 $l,r$ 内的 01 子矩阵求出通过选出一些位置进行一次操作使其变为全 $0$ 的方案中，第 $k$ 行被操作了几次。

特别的，如果没有或者有多种选择操作位置的方法，输出 $-1$。

询问之间相互独立。

输入格式

第一行三个整数 $n,m,q$。

接下来 $n$ 行，每行 $m$ 个字符，给出 01 矩阵。

接下来 $q$ 行，每行三个整数表示询问的 $l,r,k$。

输出格式

$q$ 行，每行一个整数表示对应询问的答案。

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

2
2

提示

• 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）：无特殊限制。

对于 $100\%$ 的数据，满足 $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……」

「一个天使不会交出它的翅膀除非
　跳完最后一支舞，对不对？」