Background

Define the A-distance between $(x_1,y_1)$ and $(x_2,y_2)$ as $\max\{|x_1-x_2|,|y_1-y_2|\}+1$. All distances mentioned below refer to the A-distance.

For example, the A-distance between $(1,1)$ and $(3,8)$ is $\max\{|1-3|,|1-8|\}+1=8$.

For example, the A-distance between $(46,1)$ and $(35,9)$ is $\max\{|46-35|,|1-9|\}+1=12$.

Problem Description

The territory of Country A can be seen as an $n\times m$ matrix, where the cell in row $x$ and column $y$ has coordinates $(x,y)$.

The land can be mountainous, represented by #, or flat, represented by ..

Country A has built an energy tower on every flat cell. The energy range of an energy tower is a square. If $e$ satisfies that all places whose A-distance to this energy tower is not greater than $e$ are within the territory of Country A, and those places are flat land, then $e$ is called the base energy of this energy tower.

The overall energy $E$ of an energy tower is the maximum possible value of its base energy $e$.

In particular, if there is no energy tower at a place, then the overall energy there is $E=0$. Otherwise, the overall energy there equals the overall energy of the energy tower.

Let the overall energy at row $i$ and column $j$ be $E_{i,j}$.

Let the total energy sum of a country be $\xi=\sum\limits^n_{i=1}\sum\limits_{j=1}^mE_{i,j}^2$.

You need to compute the total energy sum $\xi$ of the country.

Of course, due to special reasons (such as the effect of cosmic rays), a flat cell may suddenly turn into a mountain. The local energy tower will be destroyed, and this will also affect the overall energy $E$ of nearby energy towers.

As an advisor of Country A, the king wants you to prepare a plan: for each non-mountain cell, check what the total energy sum of the country will be after that cell becomes a mountain.

Input Format

The first line contains two integers $n,m$.

Then follows an $n\times m$ matrix. The cell in row $i$ and column $j$ is # or ., describing the terrain of Country A.

Output Format

Output a total of $n+1$ lines.

The first line contains an integer $\xi$, the initial total energy sum of Country A.

Then output an $n\times m$ matrix: the integer in row $i+1$ and column $j$ represents the total energy sum $\xi_{i,j}$ after $(i,j)$ becomes a mountain. In particular, if $(i,j)$ is originally a mountain, output $-1$.

3 4
....
...#
....

14
10 10 10 13
10 10 10 -1
10 10 10 13

5 6
...#..
#.....
......
......
...#..

39
38 38 38 -1 38 38
-1 35 32 29 32 35
35 32 29 29 32 35
35 32 29 29 32 35
35 35 35 -1 38 38

7 7
....#..
.#.....
.......
.......
.#...##
..#####
.......

51
50 50 50 50 -1 50 50
50 -1 47 44 41 44 47
50 50 44 41 38 44 47
50 50 44 41 38 44 47
50 -1 47 47 47 -1 -1
50 50 -1 -1 -1 -1 -1
50 50 50 50 50 50 50

Hint

[Sample Explanation #1]

Here are $3$ examples:

At the beginning, $E_{i,j}$ of this country is as follows:

1 1 1 1 
1 2 1 0
1 1 1 1

After $(1,1)$ becomes a mountain, $E_{i,j}$ is as follows:

0 1 1 1
1 1 1 0
1 1 1 1

After $(3,4)$ becomes a mountain, $E_{i,j}$ is as follows:

1 1 1 1
1 2 1 0
1 1 1 0

[Constraints]

For all data: $1\le n,m\le600$.

Translated by ChatGPT 5