[고등부] 2024 KOI 1차대회 대비 모의고사 (4주차)

홍윤이는 N행 M열의 격자 모양으로 이루어진 캠핑장을 차렸다.

캠핑장의 각 격자 칸에는 바위가 있을 수도 있고 빈 땅일 수도 있다.

홍윤이는 여름 방학 기간 Q일 동안 캠핑장을 운영하려고 하며 그 동안 하루에 한 팀씩 캠핑장에 방문하기로 했다.

Q개의 팀들 중 i번째 날 오는 팀은 x_i행 y_i열의 칸을 거점으로 쓰고 싶다는 요청을 보내왔다.

홍윤이는 각 팀들에 대해 거점 칸을 포함하고 바위를 포함하지 않도록 가능한 한 큰 정사각형 모양의 텐트를 칠 것이다.

(왜 그런 짓을 하는지는 모르겠지만) 바위가 있는 칸을 거점으로 쓰고 싶다는 팀들도 있으며 그 팀은 텐트를 칠 수 없다.

우리가 할 일은 홍윤이를 도와 각 팀들에게 준비될 텐트의 넓이를 미리 알려주는 것이다.

단, 텐트를 칠 수 없는 팀은 넓이를 0으로 한다.

입력

첫 줄에 N, M이 주어진다.

이후 N 줄 동안 길이 M의 문자열이 주어져 캠핑장의 정보를 나타낸다.

각 글자는 '#' 또는 '.' 이며 '#'는 바위를, '.'은 빈 땅을 나타낸다.

다음 줄에 Q가 주어진다.

이후 Q줄에 걸쳐 x_i, y_i 가 주어진다. (1 \le x_i \le N, 1 \le y_i \le M)

출력

Q줄에 걸쳐 i번째 줄에는 i번 팀이 받게 될 텐트의 넓이를 출력하라.

부분문제

캠핑
서브태스크

2초 512MB