人们常说，苹果落地，离树不远。但事实真是如此吗？

国家统计局连续 $G$ 年追踪了一个果园中苹果落下的情况。该果园可以用一个大小为 $R \times S$ 的矩阵来表示。矩阵中的每个格子可以包含不止一棵苹果树。

有趣的是，每年恰好有一个苹果落下，因此统计局决定记录下 $G$ 对数字 $(r_i, s_i)$，表示第 $i$ 年苹果落下的位置的行和列。此外，到了第二年，该位置会长出一棵新树。

你的任务是确定落下的苹果与最近的树之间的距离平方，以矩阵的单位格子为单位进行测量（我们假设苹果就是从那棵树上掉下来的）。

矩阵中格子 $(r_1, s_1)$ 和 $(r_2, s_2)$ 之间的距离计算公式为：

$$d((r_1, s_1), (r_2, s_2)) = \sqrt{(r_1 - r_2)^2 + (s_1 - s_2)^2}$$

输入格式

输入的第一行包含两个整数 $R$ 和 $S$ ($1 \le R, S \le 500$)，表示矩阵的行数和列数。

接下来的 $R$ 行，每行包含 $S$ 个字符 x 或 .。字符 . 表示空地，字符 x 表示该格子中至少有一棵树。

果园最初将包含至少一棵树。

接下来是一个整数 $G$ ($1 \le G \le 10^5$)，表示果园被观察的年数。

接下来的 $G$ 行描述了苹果落下的情况。每行包含一对整数 $(r_i, s_i)$，表示第 $i$ 年苹果落下的位置的行和列。

输出格式

输出 $G$ 个整数，表示任务中所求的距离平方，每个数占一行。

子任务

对于占总分 30% 的测试数据，满足 $G \le 500$。

样例

输入样例 1

3 3
x..
...
...
3
1 3
1 1
3 2

输出样例 1

4
0
5

输入样例 2

5 5
..x..
....x
.....
.....
.....
4
3 1
5 3
4 5
3 5

输出样例 2

8
8
4
1

说明

样例 1 说明：对于第一年落下的苹果，距离它最近的是位于格子 $(1,1)$ 的树。第二年落下的苹果恰好落在了有树的格子上，因此距离平方为 $0$。第三年落下的苹果到果园中现有的三棵树的距离均相等。