시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 256 MB 45 2 1 50.000%

문제

n×m 크기의 직사각형 그리드가 있으며, 그리드의 각 칸은 0 또는 1을 포함하고 있다. i행 j열 칸은 (i, j)로 표시한다.

"직사각형"은 네 정수 a, b, c, d (1 ≤ a ≤ c ≤ n, 1 ≤ b ≤ d ≤ m)로 정의된다. 직사각형은 {(x, y) : a ≤ x ≤ c, b ≤ y ≤ d}에 포함되는 모든 칸의 집합이다. "좋은 직사각형"은 0으로만 이루어진 "직사각형"이다.

총 q개의 쿼리를 처리하는 프로그램을 작성하시오. 각 쿼리는 다음과 같다.

주어진 직사각형에 포함되는 "좋은 직사각형"의 개수를 구한다.

입력

첫째 줄에 n, m, q (1 ≤ n, m ≤ 50, 1 ≤ q ≤ 300,000)이 주어진다. 다음에는 그리드의 정보가 n개의 줄로 주어진다. 그리드의 행과 열은 번호가 매겨져 있으며, 행은 위에서부터 아래로, 열은 왼쪽부터 오른쪽으로 매겨져 있다. 번호는 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

힌트

첫 번째 예제의 경우에 정답은 다음과 같다.

  • 1번 쿼리: 1×1 5개, 2×1 2개, 1×2 2개, 1×3 1개
  • 2번 쿼리: 1×1 1개
  • 3번 쿼리: 1×1 4개, 2×1 2개, 3×1 1개

출처