CF1186E Vus the Cossack and a Field

哥萨克 Vus 有一个 $n \times m$ 的田地，这个田地由“0”和“1”组成。他正在用这个田地构建一个无限大的田地。构建方式如下： 1. 他将当前田地取反，得到一个新的田地。也就是说，新的田地中，原来是“0”的地方变成“1”，原来是“1”的地方变成“0”。 2. 将取反后的田地拼接到当前田地的右侧。 3. 将取反后的田地拼接到当前田地的下方。 4. 将当前田地拼接到右下角。 5. 重复上述过程。 例如，若初始田地为： $\begin{matrix} 1 & 0 \\ 1 & 1 \\ \end{matrix}$ 第一次迭代后，田地变为： $\begin{matrix} 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{matrix}$ 第二次迭代后，田地变为： $\begin{matrix} 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ \end{matrix}$ 以此类推…… 我们将行从上到下编号为 $1$ 到无穷，列从左到右编号为 $1$ 到无穷。我们称子矩阵 $(x_1, y_1, x_2, y_2)$ 为所有满足 $x_1 \leq x \leq x_2$ 且 $y_1 \leq y \leq y_2$ 的格子 $(x, y)$ 组成的矩阵。 有时哥萨克需要查询某些子矩阵内所有数字的和。由于他现在很忙，所以请你帮他计算答案！

第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m \leq 1000$，$1 \leq q \leq 10^5$），分别表示初始矩阵的行数、列数和询问的数量。 接下来的 $n$ 行，每行包含 $m$ 个字符 $c_{ij}$（$0 \leq c_{ij} \leq 1$），表示矩阵中的元素。 接下来的 $q$ 行，每行包含四个整数 $x_1$、$y_1$、$x_2$、$y_2$（$1 \leq x_1 \leq x_2 \leq 10^9$，$1 \leq y_1 \leq y_2 \leq 10^9$），表示要查询的子矩阵左上角和右下角的坐标。

对于每个询问，输出一个答案。

第一个样例的过程已在题目描述中给出。 由 ChatGPT 4.1 翻译