Problem Description

JOI City is shaped like a rectangle with dimensions $ H $ kilometers north-to-south and $ W $ kilometers east-to-west, divided into $H \times W$ small squares, each measuring 1 kilometer by 1 kilometer. The small square located $ i $th from the north and $ j $th from the west is denoted as $ (i, j) $.

Each small square either has a cloud above it or does not. All clouds move 1 kilometer to the east every minute. Today, the weather is exceptionally good, so no clouds will move into JOI City from outside.

Currently, it is known whether each small square has a cloud above it or not. As a weather forecaster, you are tasked with predicting for each small square, how many minutes from now a cloud will first appear above it.

Determine for each small square how many minutes from now a cloud will first appear above it.

Input Format

The input consists of $ 1 + H $ lines.

The first line contains two integers $ H, W $ ($1 \leq H \leq 100$, $1 \leq W \leq 100$), separated by a space. This indicates that JOI City is divided into $H \times W$ small squares, each measuring 1 kilometer by 1 kilometer.

The following $ H $ lines each contain a string of $ W $ characters. The $ j $th character ($1 \leq j \leq W$) in the $ i $th line ($1 \leq i \leq H$) represents whether the small square $ (i, j) $ currently has a cloud above it. The character c (lowercase English letter) indicates the presence of a cloud, while the character . (period) indicates the absence of a cloud.

Output Format

The output consists of $ H $ lines, each containing $ W $ integers separated by spaces. The $ j $th integer in the $ i $th line ($1 \leq i \leq H$, $1 \leq j \leq W$) must represent how many minutes from now a cloud will first appear above the small square $ (i, j) $. If there is already a cloud above the small square $ (i, j) $, output $ 0 $. If no cloud will ever appear above the small square $ (i, j) $, output $ -1 $.

Do not include extra spaces at the beginning or end of each line.

Sample Input and Output

Sample Input #1

3 4
c..c
..c.
....

Sample Output #1

0 1 2 0
-1 -1 0 1
-1 -1 -1 -1

Sample Input #2

6 8
.c......
........
.ccc..c.
....c...
..c.cc..
....c...

Sample Output #2

-1 0 1 2 3 4 5 6
-1 -1 -1 -1 -1 -1 -1 -1
-1 0 0 0 1 2 0 1
-1 -1 -1 -1 0 1 2 3
-1 -1 0 1 0 0 1 2
-1 -1 -1 -1 0 1 2 3

Notes/Hints

Sample Explanation 1

In Sample Input #1, JOI City is divided into $3 \times 4$ small squares. The current cloud situation in JOI City is as follows. The top of the figure represents the north.

After that, the clouds move as follows every minute.

见题面 Input 部分

见题面 Output 部分