「MCOI-Zero / AC6-M14」Gracemeria Patrol

「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……」 「一个天使不会交出它的翅膀除非 　跳完最后一支舞，对不对？」