← 返回题目列表

Codeforces · 1186/E

E. 哥萨克 Vus 和田野

中文机器翻译题面 查看原题

哥萨克人 Vus 有一个维度为 $$$n \times m$$$ 的字段,由“0”和“1”组成。他正在从这个领域构建一个无限的领域。他是这样做的:

1. 他获取当前字段并找到一个新的反转字段。换句话说,新字段将仅在当前字段中包含“0”的地方包含“1”,而在当前字段中包含“0”的地方则包含“0”。
2. 对于当前字段,他将反转字段添加到右侧。
3. 对于当前字段,他将反转字段添加到底部。
4. 对于当前字段,他将当前字段添加到右下角。
5. 他重复一遍。

例如,如果初始字段为:

$$$\begin{矩阵} 1 & 0 & \\ 1 & 1 & \\ \end{矩阵}$$$

第一次迭代后,该字段将如下所示:

$$$\begin{矩阵} 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ \end{矩阵}$$$

第二次迭代后,该字段将如下所示:

$$$\begin{矩阵} 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{矩阵}$$$

等等...

让我们从上到下从 $$$1$$$ 到无穷大计算行,从左到右从 $$$1$$$ 到无穷大计算列。我们将子矩阵 $$$(x_1, y_1, x_2, y_2)$$$ 称为坐标为 $$$(x, y)$$$ 且满足 $$$x_1 \leq x \leq x_2$$$ 和 $$$y_1 \leq y \leq y_2$$$ 的所有数字。

哥萨克有时需要找到子矩阵中所有数字的总和。因为他现在很忙,所以他请你寻找答案!

输入

第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m \leq 1\,000$$$, $$$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$$$) — 左上角单元格和右下角单元格的坐标,您需要找到它们之间所有数字的总和。

输出

对于每个查询,打印答案。

示例

输入 #1

2 2 5
10
11
1 1 8 8
2 4 5 6
1 2 7 8
3 3 6 8
5 6 7 8

输出 #1

32
5
25
14
4

输入 #2

2 3 7
100
101
4 12 5 17
5 4 9 4
1 4 13 18
12 1 14 9
3 10 7 18
3 15 12 17
8 6 8 12

输出 #2

6
3
98
13
22
15
3

注意

第一个示例在图例中进行了解释。