---

题目描述

题目译自 NordicOI 2018 T1「Nordic Camping」

在北欧高地露营时，拥有可靠的水源是生死攸关的事情。传统上，北欧露营者总是把帐篷搭在水源上方，这样可以随时取水而不必走出帐篷。另一个奇怪的传统是，他们只使用方形帐篷。

北欧高地的露营地非常崎岖不平。Jon 正在建立一个新的露营地，并已经勘测了所有可用的地点。将露营地建模为一个 $N \times M$ 的网格，Jon 给出了所有崎岖不平、无法使用的格子列表。现在，Jon 想知道在他的露营地上，覆盖给定水源的最大方形帐篷能有多大，只能使用平滑、可用的格子。

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

上图第二个样例的示意图，展示了覆盖水源 $(3,2)$ 的最大方形帐篷的面积。这也恰好是覆盖水源 $(5,4)$ 的最大方形帐篷。

---

输入格式

• 第一行包含两个用空格分隔的整数 $N$ 和 $M$ $(1 \leq N,M)$。
• 接下来是 $N$ 行，每行包含 $M$ 个字符，表示网格。每个字符要么是 #，要么是 .，其中 . 表示露营地的平滑区域，# 表示崎岖不平、无法使用的区域。
• 然后是一行，包含一个整数 $Q$，表示 Jon 考虑的水源数量。
• 接下来的 $Q$ 行，每行包含两个整数 $x$ 和 $y$ $(1 \leq x \leq N, 1 \leq y \leq M)$，表示水源的位置位于网格中第 $x$ 行第 $y$ 列。

---

输出格式

对于 Jon 考虑的每个水源，按照输入的顺序，输出覆盖该水源的最大方形帐篷的面积。

注意，帐篷不能部分覆盖一个格子。要么完全覆盖，要么完全不覆盖。

---

样例 1

输入

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

输出

4
1

---

样例 2

输入

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

输出

9
4
9
0
1

---

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
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$

---