← 返回题目列表

Codeforces · 372/B

B. 计算矩形很有趣

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

有一个 n × m 的矩形网格,网格的每个单元格包含一个整数:零或一。我们将第 i 行第 j 列的单元格称为 (i, j)。

让我们将“矩形”定义为四个整数 a、b、c、d (1 ≤ a ≤ c ≤ n;1 ≤ b ≤ d ≤ m)。矩形表示网格的一组单元格 {(x, y):a ≤ x ≤ c, b ≤ y ≤ d}。让我们将“好矩形”定义为仅包含带有零的单元格的矩形。

您应该回答以下 q 个查询:计算所有单元格都位于给定矩形中的好矩形的数量。

输入

第一行有三个整数:n、m、q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·105)。接下来的 n 行中的每一行都包含 m 个字符——网格。考虑网格行从上到下编号,网格列从左到右编号。列和行都从 1 开始编号。

接下来的 q 行中的每一行都包含一个查询 - 描述当前矩形的四个整数 a、b、c、d (1 ≤ a ≤ c ≤ n;1 ≤ b ≤ d ≤ m)。

输出

对于每个查询输出一个答案 - 单独行中的单个整数。

示例

输入 #1

5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3

输出 #1

10
1
7
34
5

输入 #2

4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7

输出 #2

3
1
16
27
52

注意

对于第一个示例,有一个 5 × 5 矩形网格,第一个、第二个和第三个查询如下图所示。

- 对于第一个查询,有 10 个好的矩形,五个 1 × 1、两个 2 × 1、两个 1 × 2 和一个 1 × 3。
- 对于第二个查询,只有一个 1 × 1 的好矩形。
- 对于第三个查询,有 7 个好的矩形,四个 1 × 1,两个 2 × 1,一个 3 × 1。