Description

给定一个 $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$。

询问之间相互独立。

Input Format

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

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

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

Output Format

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

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

对于 $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……」

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