북유럽 캠핑

북유럽 국가의 고지대에서 캠핑할 때, 신뢰할 수 있는 물 공급원을 확보하는 것은 생사가 달린 문제가 될 수 있다. 전통적으로 북유럽의 캠핑객들은 밖으로 나가지 않고도 언제든 물을 길을 수 있도록 항상 수원 위에 텐트를 쳐 왔다. 북유럽 사람들의 또 다른 기이한 전통은 텐트에 관한 것이다. 이들은 정사각형 텐트만 사용한다.

북유럽 고지대의 야영지는 지면이 매우 거칠고 바위가 많을 수 있다. Jon은 현재 새로운 야영지를 조성하고 있으며, 야영지에서 사용할 수 있는 모든 지점을 조사했다. 야영지를 $N$ × $M$ 격자로 모델링하여, Jon은 거칠어서 사용할 수 없는 모든 칸의 목록을 당신에게 제공한다. 이제 Jon은 매끄럽고 사용할 수 있는 칸만 이용하면서 주어진 수원을 덮도록 자신의 야영지에 칠 수 있는 가장 큰 텐트를 알아내고자 한다.

각 수원에 대해, 그 특정 수원을 덮도록 칠 수 있는 가장 큰 정사각형 텐트의 크기를 Jon이 구할 수 있도록 도와줄 수 있는가?

두 번째 예제 테스트 케이스와 $(3,2)$의 수원을 덮는 가장 큰 정사각형 텐트의 면적. 이는 $(5,4)$의 수원을 덮는 가장 큰 정사각형 텐트이기도 하다.

채점

제출한 풀이는 여러 하위 과제로 구성된 테스트 세트로 채점된다. 하나의 하위 과제는 여러 테스트 케이스로 구성된다. 해당 하위 과제의 점수를 얻으려면, 제출한 풀이가 그 하위 과제에 포함된 모든 테스트 케이스를 통과해야 한다.

하위 과제 | 점수 | 제약 조건

1 | 20 | $N,M \leq 50$, $Q\leq 1000$

2 | 25 | $N,M \leq 800$, $K\leq 10^5$, $Q\leq 10^5$

3 | 20 | $N\leq 10$, $M \leq 2000$, $Q\leq 500$

4 | 35 | $N,M \leq 2000$, $K\leq 10^5$, $Q\leq 10^5$

입력의 첫째 줄에는 공백으로 구분된 두 정수 $N$와 $M$가 주어진다 ($1 \leq N,M$). 이어지는 $N$개의 줄은 각각 $M$개의 문자로 이루어지며, 격자를 나타낸다. 각 문자는 #`' 또는 .'이며, ``.'는 야영지의 매끄러운 영역을 나타내고 ``#`'는 바위가 많아 사용할 수 없는 영역을 나타낸다.

그다음 줄에는 Jon이 고려하고 있는 수원의 개수를 나타내는 하나의 정수 $Q$가 주어진다. 이어지는 $Q$개의 각 줄에는 두 정수 $x$와 $y$가 주어지며 ($1 \leq x \leq N$, $1 \leq y \leq M$), 수원의 위치 $(x,y)$를 나타낸다(격자의 $x$행, $y$열에 있는 수원).

Jon이 고려하고 있는 각 수원에 대해, 입력에 주어진 것과 같은 순서로, 매끄럽고 사용할 수 있는 칸 위에 치면서 해당 수원을 덮을 수 있는 가장 큰 정사각형 텐트의 바닥 면적을 출력한다.

텐트가 칸의 일부만 덮도록 칠 수는 없다는 점에 유의한다. 텐트는 칸을 완전히 덮거나, 그 칸과 전혀 겹치지 않아야 한다.