有一个 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。