题目背景

译自 Nordic Olympiad in Informatics 2018 Nordic Camping。

upd 2025/1/3 13:18：本题原题未说明 $K$ 代表什么。搬题人经过 assert 认为是网格中 # 的个数。

题目描述

在北欧高地露营时，能否找到可靠的水源是生死攸关的问题。传统上，北欧露营者总是将帐篷搭在水源上，这样可以随时取水，而不必出门。北欧人的另一个奇怪传统是他们的帐篷。他们只使用正方形帐篷。

北欧高地的营地可能非常崎岖。Jon 正在设置一个新营地，他已经调查了所有可用的区域，并将无法使用的区域标记出来。我们可以将营地建模为一个 $N \times M$ 的网格，其中每个格子要么是崎岖的（不可用），要么是平坦的（可用）。

对于每一个水源，你能帮助 Jon 确定能够覆盖该水源的最大正方形帐篷的大小吗？

图1：第二个样例以及覆盖水源 $(3, 2)$ 的最大正方形帐篷的区域。这也恰好是覆盖水源 $(5, 4)$ 的最大正方形帐篷。

输入格式

输入的第一行包含用空格分隔的两个整数 $N$ 和 $M$（$1 \leq N,M$）。接下来是 $N$ 行，每行由 $M$ 个字符组成，代表网格。每个字符都是 # 或 .，其中 . 表示露营地的平坦的可用区域，# 表示崎岖的不可用区域。

接下来是一行，其中只有一个整数 $Q$（$1\leq Q$），即 Jon 考虑的水源数量。接下来的 $Q$ 行每行包含两个整数 $x$ 和 $y$ ($1 \leq x \leq N$，$1 \leq y \leq M$)，表示水源的位置 $(x, y)$（即网格中第 $x$ 行，第 $y$ 列是水源）。

输出格式

对于 Jon 考虑的每一个水源，按照与输入相同的顺序，输出可以搭建在平坦的可用单元格上以覆盖特定水源的最大正方形帐篷的面积。

请注意，帐篷不能只覆盖一个格子的部分位置。要么完全覆盖，要么与格子的交为空。

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

4
1

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

9
4
9
0
1

提示

你的解法将在一组子任务上进行评分。每个子任务包含多个测试用例。要获得子任务的分数，你的解法必须通过子任务中的所有测试用例。