哥萨克人 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
注意
第一个示例在图例中进行了解释。