#P17619. Gracemeria Patrol

Gracemeria Patrol

1.5s 512M

题目描述

给定一个 n×mn\times m 的 01 矩阵,每一次操作可以改变一个位置以及其上面、左边、右边的值。如果原值是 00,则改变之后变成 11;否则变成 00。

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

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

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

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

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

询问之间相互独立。

输入格式

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

接下来 nn 行,每行 mm 个字符,给出 01 矩阵。

接下来 qq 行,每行三个整数表示询问的 l,r,kl,r,k。

输出格式

qq 行,每行一个整数表示对应询问的答案。

输入输出样例 #1

输入 #1

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

输出 #1

2
2

说明/提示

  • Subtask 1(10 pts):n,m≤3,q≤10n,m\leq 3,q\leq 10。
  • Subtask 2(20 pts):n,m,q≤10n,m,q\leq 10。
  • Subtask 3(20 pts):n,q≤50,m≤10n,q\leq 50,m\leq 10。
  • Subtask 4(20 pts):n,q≤104,m≤10n,q\leq 10^4,m\leq 10。
  • Subtask 5(30 pts):无特殊限制。

对于 100%100\% 的数据,满足 1≤n≤5×1041\leq n\leq 5\times 10^4,1≤m≤501\leq m\leq 50,1≤q≤5×1051\leq q\leq 5\times 10^5,1≤l≤k≤r≤n1\leq l\leq k\leq r\leq n。