노르딕 캠핑

북유럽 고지대에서 캠핑할 때는 믿을 수 있는 식수원을 확보하는 일이 생사를 가를 수 있다. 북유럽 캠핑객들은 전통적으로 텐트 안에서 언제든 물을 길어 올 수 있도록 식수원을 덮는 위치에 텐트를 친다. 북유럽 사람들의 또 다른 독특한 전통은 텐트인데, 정사각형 텐트만 사용한다.

북유럽 고지대의 캠핑장은 거칠고 바위가 많아 울퉁불퉁할 수 있다. 욘은 새로운 캠핑장을 조성하면서 캠핑장에서 사용할 수 있는 모든 지점을 측량했다. 캠핑장을 $N$행 $M$열 격자로 모델링하면, 욘은 거칠어서 사용할 수 없는 셀의 목록을 제공한다. 이제 욘은 매끄럽고 사용 가능한 셀만을 써서 주어진 식수원을 덮을 수 있는 가장 큰 텐트가 무엇인지 알아내려 한다.

각 식수원에 대해, 그 식수원을 덮도록 칠 수 있는 가장 큰 정사각형 텐트의 크기를 구하라.

그림 1: 식수원 $(3, 2)$를 덮는 가장 큰 정사각형 텐트의 영역. 이 텐트는 식수원 $(5, 4)$를 덮는 가장 큰 정사각형 텐트이기도 하다.

입력의 첫 줄에는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다 ($1 \le N$, $1 \le M$). 이어서 $N$개의 줄이 주어지며, 각 줄은 $M$개의 문자로 이루어져 캠핑장 지도를 나타낸다. 각 문자는 . 또는 #이며, .는 사용 가능한 셀을, #는 바위투성이의 사용 불가능한 셀을 나타낸다.

그 다음 줄에는 욘이 고려 중인 식수원의 개수인 정수 $Q$가 주어진다. 이어지는 $Q$개의 각 줄에는 두 정수 $x$와 $y$가 주어지며 ($1 \le x \le N$, $1 \le y \le M$), 격자의 $x$행 $y$열에 식수원이 있음을 나타낸다.

욘이 고려 중인 각 식수원에 대해, 입력에 주어진 순서대로 매끄럽고 사용 가능한 셀만으로 이루어져 그 식수원을 덮는 가장 큰 정사각형 텐트의 바닥 면적을 출력한다. 식수원이 바위 셀에 있으면 칠 수 있는 텐트가 없으므로 $0$을 출력한다.

텐트는 셀을 비스듬히 걸쳐서 칠 수 없다. 각 셀을 완전히 덮거나 전혀 겹치지 않아야 한다.