Description

You are given an $n \times m$ matrix, where apple trees are represented by x, and empty cells are represented by ..

There are $g$ years. Each year, an apple falls from the sky onto the coordinate $(x_i, y_i)$. You need to output the square of the distance from this apple to the nearest apple tree. Of course, after one year, this apple will grow into a new apple tree, and it will be included in the computation for the apple that falls in the next year.

Input Format

The first line contains two positive integers $n, m$, representing the matrix's height and width.

The next $n$ lines each contain $m$ characters, consisting only of x and ., describing the matrix.

Then a positive integer $g$ is given, representing the number of years.

The next $g$ lines each contain two positive integers $x_i, y_i$, representing the position where the apple falls each year.

Output Format

Output $g$ lines in total. Each line contains one integer, representing the square of the distance from the falling apple to the nearest apple tree at that time.

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

4
0
5

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

8
8
4
1

Hint

For $30\%$ of the testdata, $1 \leq g \leq 500$.

For $100\%$ of the testdata, $1 \leq n, m \leq 500$, $1 \leq g \leq 10^5$. It is guaranteed that the initial matrix contains at least one apple tree.

Distance formula: $d((x_1,y_1),(x_2,y_2))=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$.

Translated from COCI 2014/2015 CONTEST #5。

Translated by ChatGPT 5