CF372B.Counting Rectangles is Fun

There is an n × m rectangular grid, each cell of the grid contains a single integer: zero or one. Let's call the cell on the i-th row and the j-th column as (i, j).

Let's define a "rectangle" as four integers a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m). Rectangle denotes a set of cells of the grid {(x, y) :  a ≤ x ≤ c, b ≤ y ≤ d}. Let's define a "good rectangle" as a rectangle that includes only the cells with zeros.

You should answer the following q queries: calculate the number of good rectangles all of which cells are in the given rectangle.

有一个 $n \times m$ 的矩形网格，网格的每个单元格中包含一个整数：0 或 1。我们将第 $i$ 行、第 $j$ 列的单元格记为 $(i, j)$。

我们定义一个“矩形”为四个整数 $a,\,b,\,c,\,d$（满足 $1 \le a \le c \le n$；$1 \le b \le d \le m$）。该矩形表示网格中的一组单元格 $\{(x, y) : a \le x \le c,\, b \le y \le d\}$。我们称一个“好矩形”为仅包含值为 0 的单元格的矩形。

你需要回答以下 $q$ 个查询：对每个给定的矩形，计算完全位于该矩形内部的“好矩形”的数量。

There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·105). Each of the next n lines contains m characters — the grid. Consider grid rows are numbered from top to bottom, and grid columns are numbered from left to right. Both columns and rows are numbered starting from 1.

Each of the next q lines contains a query — four integers that describe the current rectangle, a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m).

第一行包含三个整数：$n$、$m$ 和 $q$（$1 ≤ n, m ≤ 40$，$1 ≤ q ≤ 3·10^5$）。接下来的 $n$ 行，每行包含 $m$ 个字符——表示网格。网格的行从上到下编号，列从左到右编号；行列编号均从 $1$ 开始。

接下来的 $q$ 行，每行包含一个查询——四个整数，描述当前矩形区域：$a$、$b$、$c$、$d$（$1 ≤ a ≤ c ≤ n$；$1 ≤ b ≤ d ≤ m$）。

For each query output an answer — a single integer in a separate line.

对于每个查询，输出一个答案——每行一个整数。

For the first example, there is a 5 × 5 rectangular grid, and the first, the second, and the third queries are represented in the following image.

• For the first query, there are 10 good rectangles, five 1 × 1, two 2 × 1, two 1 × 2, and one 1 × 3.
• For the second query, there is only one 1 × 1 good rectangle.
• For the third query, there are 7 good rectangles, four 1 × 1, two 2 × 1, and one 3 × 1.

第一个样例中，有一个 $5 \times 5$ 的矩形网格，第一、第二和第三个查询如下图所示。

• 对于第一个查询，共有 10 个“好矩形”：五个 $1 \times 1$，两个 $2 \times 1$，两个 $1 \times 2$，以及一个 $1 \times 3$。
• 对于第二个查询，仅有一个 $1 \times 1$ 的“好矩形”。
• 对于第三个查询，共有 7 个“好矩形”：四个 $1 \times 1$，两个 $2 \times 1$，以及一个 $3 \times 1$。