Good Rectangles

You are given an $n \times m$ grid. Every cell holds 0 or 1. The cell in row $i$ and column $j$ is written $(i, j)$.

Four integers $a$, $b$, $c$, $d$ with $1 \le a \le c \le n$ and $1 \le b \le d \le m$ define a rectangle, the set $\{(x, y) : a \le x \le c,\ b \le y \le d\}$ of all cells inside those bounds. A rectangle is good if every cell in it holds 0.

Write a program that answers $q$ queries. Each query gives one rectangle and asks how many good rectangles are fully contained in it.

The first line contains $n$, $m$, $q$ ($1 \le n, m \le 50$, $1 \le q \le 300\,000$).

Each of the next $n$ lines contains a string of length $m$ made only of the characters 0 and 1, describing one row of the grid. Rows are numbered from 1 top to bottom, and columns are numbered from 1 left to right.

Each of the next $q$ lines contains one query, given as four integers $a$, $b$, $c$, $d$ ($1 \le a \le c \le n$, $1 \le b \le d \le m$) describing a rectangle.

For each query, print the answer on its own line.

The answers to the first sample break down like this.

• Query 1: five of size $1 \times 1$, two of size $2 \times 1$, two of size $1 \times 2$, one of size $1 \times 3$
• Query 2: one of size $1 \times 1$
• Query 3: four of size $1 \times 1$, two of size $2 \times 1$, one of size $3 \times 1$