该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

【题目描述】

FJ的棋盘地被划分成R行C列，共R×C个格子。一开始时，如果某个格子有棋子，那么用‘x’表示，如果没有棋子则用‘.’表示。现在FJ有Q个操作，每个操作的格式是给出两个整数：a 和 b，表示询问到目前为止，距离第a行第b列格子最近的棋子在哪里？输出该棋子所在格子与第a行第b列格子的距离。当你输出该距离之后，FJ在第a行第b列的格子增加一个棋子。 现在给出两个格子的距离计算公式：记第a行第b列的格子是（a,b)，第c行第d列的格子是（c,d)，那么格子(a,b)与格子(c,d)的距离=（a-c) × (a-c) + (b-d)×(b-d)。

输入格式

【输入格式】d.in

第一行，R和C。 1 <= R, C <= 500。

接下来是R行C列棋盘，每个元素要么是x’，要么是‘.’，数据保证至少有一个棋子。

接下来一行，是一个整数Q，表示总共有Q个操作。 1<=Q<=100000。

接下来有Q行，每行表示一个操作，格式是两个整数：a和b。意义如题目所示。

输出格式

【输出格式】d.out

共Q行，每行输出一个距离。

数据规模

【数据规模】

对于30%的数据，Q <= 500。

输入样例 d.in

输出样例 d.out

样例解释

3 3

x..

...

...

3

1 3

1 1

3 2

4

0

5

棋盘是3行3列，一开始只有第1行第1列的格子有棋子。

FJ总共有3个操作，第一个操作：询问离第1行第3列最近的棋子所在格子与第1行第3列格子的距离是多少？由于到目前为止只有第1行第1列有棋子，那么答案肯定就是：(1-1)(1-1) + (1-3)(1-3)=4。所以你要输出4。然后FJ在第1行第3列的格子增加一个棋子。

第二个操作：询问离第1行第1列最近的棋子所在格子与第1行第1列格子的距离是多少？虽然到目前为止已经有了两个棋子，但显然， 第1行第1列的棋子更近些，那么答案肯定就是：(1-1)(1-1) + (1-1)(1-1)=0。所以你要输出0。然后FJ在第1行第1列的格子增加一个棋子。

第三个操作：询问离第3行第2列最近的棋子所在格子与第3行第2列格子的距离是多少？虽然到目前为止已经有了3个棋子，答案肯是：(1-3)(1-3) + (1-2)(1-2)=5。所以你要输出5。然后FJ在第3行第2列的格子增加一个棋子。