좋은 직사각형

각 칸에 0 또는 1이 적힌 $n \times m$ 크기의 격자가 있다. 위에서 $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$개 처리하는 프로그램을 작성하시오. 각 쿼리는 직사각형을 하나 주고, 그 직사각형에 완전히 포함되는 좋은 직사각형의 개수를 묻는다.

첫째 줄에 $n$, $m$, $q$가 주어진다 ($1 \le n, m \le 50$, $1 \le q \le 300\,000$).

다음 $n$개 줄에 격자가 주어진다. 각 줄은 0과 1로만 이루어진 길이 $m$의 문자열이다. 행은 위에서 아래로, 열은 왼쪽에서 오른쪽으로 1번부터 번호를 매긴다.

다음 $q$개 줄에 쿼리가 한 줄에 하나씩 주어진다. 각 줄에는 직사각형을 나타내는 네 정수 $a$, $b$, $c$, $d$가 주어진다 ($1 \le a \le c \le n$, $1 \le b \le d \le m$).

쿼리마다 답을 한 줄에 하나씩 출력한다.

첫 번째 예제의 답은 이렇게 나온다.

• 1번 쿼리: $1 \times 1$이 5개, $2 \times 1$이 2개, $1 \times 2$가 2개, $1 \times 3$이 1개
• 2번 쿼리: $1 \times 1$이 1개
• 3번 쿼리: $1 \times 1$이 4개, $2 \times 1$이 2개, $3 \times 1$이 1개