말 서식지

해럴드는 수백 마리의 말이 있는 거대한 서식지를 물려받았다! 그는 아리조나의 승마 역사를 기리는 반년 단위 행사인 Bareback Arizona Phoenix Cowboys에 말 몇 마리를 출전시키려 한다. 그래서 해럴드는 말들을 Hurdle Hopping 종목에 등록했고, 훈련 프로그램 운영을 도와 달라고 요청했다.

Hurdle Hopping 코스는 배치가 여러 가지이고, 배치마다 필요한 직사각형 넓이가 다르다. 하지만 서식지의 땅이 모두 코스에 적합한 것은 아니다. 말은 다양한 상황에 적응하려면 여러 곳에서 훈련해야 하므로, 코스는 여러 위치에 다시 만들 수 있어야 한다.

서식지는 단위 정사각형으로 이루어진 격자 지도로 주어진다. 각 칸은 그 땅이 코스에 적합한지 여부를 나타낸다. 질문 목록에 답하라. 각 질문은 주어진 크기의 Hurdle Hopping 코스를 놓을 수 있는 위치가 서식지 안에 모두 몇 곳인지 묻는다.

입력은 다음과 같다.

• 세 정수 $r$, $c$, $q$($1 \leq r,c \leq 9 \cdot 10^6$, $r \cdot c \leq 9 \cdot 10^6$, $1 \leq q \leq 10^5$)가 한 줄에 주어진다. 각각 격자의 행 수, 열 수, 질문 수이다.
• 이어서 $c$개의 문자로 이루어진 줄이 $r$개 주어진다. 각 문자는 해당 칸이 코스에 적합한 땅이면 '.', 아니면 '#'이다.
• 이어서 두 정수 $h$와 $w$($1 \leq h \leq r$, $1 \leq w \leq c$)가 한 줄에 주어지며, 이는 높이 $h$(격자의 행 수), 너비 $w$(격자의 열 수)인 Hurdle Hopping 코스의 개수를 묻는 질문이다.

$q$개의 질문마다, 요청된 높이 $h$(격자의 행 수)와 너비 $w$(격자의 열 수)인 Hurdle Hopping 코스를 격자에 맞춰 놓을 수 있는 위치의 개수를 출력한다.