P7663 [COCI 2014/2015 #5] JABUKE

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.

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 $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.

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](https://hsin.hr/coci/archive/2014_2015/contest5_tasks.pdf)。 Translated by ChatGPT 5