#Summer24008. Apple Tree

Apple Tree

Apple Tree

题目描述

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

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

输入格式

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

接下来 nn 行,每行 mm 个字符,字符仅含 x.,表示该矩阵。

接下来一个正整数 gg,表示年份。

接下来 gg 行每行两个正整数 xi,yix_i,y_i,表示每年苹果下落的位置。

输出格式

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

样例 #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%30\% 的数据,1g5001 \leq g \leq 500

对于 100%100\% 的数据,1n,m500,1g1041\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}$。