회의실 빈자리 지도

문제

큰 강당의 좌석 배치가 R행 C열 격자로 주어진다. '#' 은 이미 누가 맡은 자리, '.' 은 빈자리다. 팀 단위로 자리를 잡으려는 사람들이 직사각형 영역을 하나씩 묻는다. 각 질문마다 그 영역 안의 빈자리 수를 답하라. 영역은 왼쪽 위 칸 (r1, c1) 과 오른쪽 아래 칸 (r2, c2) 으로 주어지며 두 칸을 포함한다. 행과 열 번호는 1부터 센다.

입력

첫째 줄에 R 과 C 가 주어진다. (1 ≤ R, C ≤ 300)

다음 R개 줄에 길이 C 인 문자열이 주어진다. 문자열은 '#' 과 '.' 로만 이루어져 있다.

그다음 줄에 질문 수 Q (1 ≤ Q ≤ 10,000) 가 주어지고, 다음 Q개 줄에 r1 c1 r2 c2 가 주어진다. (1 ≤ r1 ≤ r2 ≤ R, 1 ≤ c1 ≤ c2 ≤ C)

출력

질문마다 한 줄에 빈자리 수를 출력한다.

3 4
#..#
....
##.#
3
1 1 3 4
2 2 3 3
1 1 1 1

7
3
0

출처: Devin.KR 자체 제작