Apple Tree

题目描述

给你一个 $n \times m$ 的矩阵，其中苹果树用 x 表示，空地用 . 表示。

有 $g$ 年，每年都会从天而降一个苹果，落在坐标 $(x_i,y_i)$ 上，要求出这个苹果离最近一棵苹果树的距离的平方。当然，一年后这个苹果会长成新的一颗苹果树，并参与一年后落下的那个苹果的计算。

输入格式

第一行两个正整数 $n,m$，表示矩阵的长，宽。

接下来 $n$ 行，每行 $m$ 个字符，字符仅含 x 和 .，表示该矩阵。

接下来一个正整数 $g$，表示年份。

接下来 $g$ 行每行两个正整数 $x_i,y_i$，表示每年苹果下落的位置。

输出格式

一共 $g$ 行，每行一个整数，表示每个苹果下落时离最近一棵苹果树的距离的平方。

样例 #1

样例输入 #1

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

样例输出 #1

4
0
5

样例 #2

样例输入 #2

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

样例输出 #2

8
8
4
1

提示

对于 $30\%$ 的数据，$1 \leq g \leq 500$。

对于 $100\%$ 的数据，$1\leq n,m \leq 500,1 \leq g \leq 10^4$，保证初始矩阵至少包含一棵苹果树。

距离计算公式：$d((x_1,y_1),(x_2,y_2))=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$。