A9366 | 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.

There are three integers in the first line: $n$ , $m$ and $q$ ( $1<=n,m<=40,1<=q<=3·10^{5}$ ). 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)$ .

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