수족관 조명 점검 구역

문제

수족관 관리자는 여러 수조 위에 설치된 조명을 점검하고 있다. 조명 배치는 R개의 행과 C개의 열로 이루어진 직사각형 표로 표현한다. 표의 각 칸에는 조명 하나가 있으며, 점검이 필요한 조명은 1, 점검이 필요하지 않은 조명은 0으로 기록되어 있다. 행 번호는 위에서부터 1번부터 R번까지, 열 번호는 왼쪽에서부터 1번부터 C번까지 붙어 있다. 이 표는 점검 계획을 세우기 직전에 조사한 상태를 나타낸다. 관리자는 작업자가 이동할 범위를 정하기 위해 여러 개의 직사각형 구역을 후보로 만들었다. 하나의 후보 구역은 왼쪽 위 칸의 행과 열, 오른쪽 아래 칸의 행과 열로 지정한다. 지정한 두 모서리를 포함하여 그 사이에 있는 모든 칸이 해당 구역에 속한다. 구역의 높이나 너비가 1이어도 되며, 두 모서리가 같은 칸이면 조명 하나만 포함하는 구역이다. 모든 후보는 표 안에 완전히 들어오도록 주어진다. 각 후보에 대해 알고 싶은 값은 그 구역 안에서 점검이 필요한 조명의 개수이다. 조명이 없는 칸은 없으므로 구역 안의 1을 모두 세면 된다. 구역이 넓다고 해서 모든 조명을 점검 대상으로 세는 것은 아니며, 값이 0인 칸은 개수에 포함하지 않는다. 구역 안에 1이 하나도 없으면 그 후보의 답은 0이다. 전체 표가 하나의 후보로 주어질 수도 있다. 후보 구역들은 서로 겹치거나 완전히 같을 수 있다. 이들은 각각 독립적인 계획안이므로 앞선 후보의 답을 구했다고 해서 조명의 상태가 바뀌지는 않는다. 또한 한 후보에서 센 조명을 다른 후보에서 다시 세어도 된다. 실제 수리나 상태 변경은 모든 계획안을 검토한 뒤에 진행하므로 입력을 처리하는 동안 표의 값은 고정되어 있다. 주어진 순서대로 모든 후보 구역의 점검 대상 조명 수를 계산하여 출력한다.

입력

첫째 줄에 정수 R, C, Q가 공백으로 구분되어 주어진다. 1 ≤ R, C ≤ 200이며 1 ≤ Q ≤ 10,000이다.
다음 R개 줄에 조명 상태가 주어진다. 각 줄은 공백 없이 0과 1로만 이루어진 길이 C의 문자열이며, 위쪽 행부터 차례대로 주어진다.
다음 Q개 줄에 후보 구역을 나타내는 정수 r_1, c_1, r_2, c_2가 공백으로 구분되어 주어진다. 1 ≤ r_1 ≤ r_2 ≤ R이고 1 ≤ c_1 ≤ c_2 ≤ C이다.

출력

각 후보 구역 안에 있는 값이 1인 칸의 개수를 입력 순서대로 한 줄에 하나씩 출력한다. 해당하는 칸이 없으면 0을 출력한다.

3 4 3
1010
0110
1101
1 1 3 4
1 2 2 3
3 3 3 3

7
3
0

1 1 2
0
1 1 1 1
1 1 1 1

0
0

2 3 3
111
111
1 2 2 2
2 1 2 3
1 1 2 3

2
3
6

출처: Devin.KR 자체 제작