Energy Towers in A Country

A country, called A, can be represented as an n×m grid where the cell in the x-th row and y-th column is denoted by (x,y).

Each cell is either plain (represented by .) or mountain (represented by #). On every plain a tower is built. Each tower collects energy from a square region centered at itself. For a tower located at (i,j) and an integer e ≥ 0, if every cell within the square region defined by

[ {(x,y) \mid \max(|x-i|,|y-j|)\le e}]

is inside the grid and is a plain cell, then e is called a valid base energy for that tower. The composite energy of a tower is defined as the maximum valid e for it. (Note that if the cell is a mountain, there is no tower and its energy is defined to be 0.)

The total energy of the country is defined as

[ \xi = \sum_{i=1}^{n} \sum_{j=1}^{m} E_{i,j}^2, ]

where E_i,j is the composite energy of the tower (if any) at cell (i,j).

Due to certain cosmic events, a plain cell might suddenly turn into a mountain. When that happens, the tower on that cell is destroyed and the energy collection range of nearby towers may be affected. As an advisor to the king of A, you are asked to prepare a contingency plan. For each plain cell in the original grid, if that cell were to turn into a mountain (and other cells remain unchanged), compute the new total energy of the country.

Note on the energy update: Suppose a tower originally has composite energy E. If a mountain appears at a cell whose Chebyshev distance from the tower is d (with d ≤ E), then the tower’s new composite energy will become d−1 (if d > 0). Also, if the tower itself is replaced (i.e. the tower’s own cell turns to mountain) then its energy becomes 0.

inputFormat

The first line contains two space‐separated integers n and m, representing the number of rows and columns.

The following n lines each contain a string of length m consisting of characters . and # that describe the grid.

outputFormat

For every plain cell in the input grid (in row‐major order), output one line containing a single integer: the total energy of the country after that cell is turned into a mountain.

sample

3 3
...
...
...

0
0
0
0
0
0
0
0
0