Background

The A distance between points \((x_1, y_1)\) and \((x_2, y_2)\) is defined as \(\max\{|x_1 - x_2|, |y_1 - y_2|\} + 1\). The term "distance" in this context refers to the A distance.

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

Another 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 represented as an \(n \times m\) matrix, where the coordinates of the cell in the \(x\)-th row and \(y\)-th column are \((x, y)\).

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

Country A has built an energy tower on every flat land. The energy collection range of an energy tower is a square. If \(e\) is such that the area within the A distance not exceeding \(e\) from the tower is within Country A's territory and is flat land, then \(e\) is considered the benchmark energy of that tower.

The comprehensive energy \(E\) of a tower is the maximum value of its benchmark energy \(e\).

Specifically, if there is no energy tower at a location, the comprehensive energy \(E\) at that location is \(0\); otherwise, it is the comprehensive energy of the tower.

Let the comprehensive energy at the \(i\)-th row and \(j\)-th column be \(E_{i,j}\).

The total energy of the country \(\xi\) is defined as \(\sum_{i=1}^n \sum_{j=1}^m E_{i,j}^2\).

You need to calculate the total energy of the country \(\xi\).

Due to special reasons (such as cosmic radiation), a flat land may suddenly turn into mountainous terrain, destroying the local energy tower and affecting the comprehensive energy \(E\) of nearby towers.

As an advisor to Country A, the king wants you to prepare a plan to determine the total energy of the country after each non-mountainous point becomes mountainous.

Input Format

The first line contains two integers \(n\) and \(m\).

Following is an \(n \times m\) matrix where each cell is either # or ., describing the terrain of Country A.

Output Format

The output consists of \(n + 1\) lines.

The first line contains an integer \(\xi\), representing the initial total energy of Country A.

The next \(n\) lines form an \(n \times m\) matrix. The \((i+1)\)-th line and \(j\)-th integer represent the total energy of the country \(\xi_{i,j}\) after the point \((i, j)\) becomes mountainous. If \((i, j)\) was originally mountainous, output \(-1\).

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

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

Output Sample #2

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

Input Sample #3

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

Output Sample #3

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

Notes

Sample Explanation #1

Here are three examples:

Initially, the \(E_{i,j}\) of the country is:

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

After \((1, 1)\) becomes mountainous, the \(E_{i,j}\) is:

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

After \((3, 4)\) becomes mountainous, the \(E_{i,j}\) is:

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

Data Range

For all data, it is guaranteed that \(1 \le n, m \le 600\).

见题面 Input 部分

见题面 Output 部分