Apple Trees and Falling Apples

You are given an n x m matrix representing a field. In the matrix, an apple tree is denoted by an x and an empty cell is denoted by a period ..

There are g years. In each year, an apple falls from the sky at coordinates ((x_i, y_i)). For each falling apple, you need to compute the square of the Euclidean distance from this apple to its nearest apple tree. Note that after each year, the fallen apple grows into a new apple tree and will participate in the distance calculation for subsequent apples.

The Euclidean distance squared between two points ((a, b)) and ((c, d)) is given by ((a-c)^2 + (b-d)^2).

inputFormat

The first line contains two integers n and m indicating the number of rows and columns of the matrix. The next n lines each contain a string of length m, consisting of characters 'x' (apple tree) and '.' (empty cell).

The next line contains an integer g, the number of years. Each of the following g lines contains two integers x_i and y_i representing the coordinates where the apple falls in that year. It is assumed that the matrix uses 1-indexed coordinates.

outputFormat

Output g lines, each containing a single integer: the square of the distance from the falling apple in that year to its nearest apple tree at that moment.

sample

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

0
0