JOI City has the shape of a rectangle of $H$ kilometers in the north-south direction and $W$ kilometers in the east-west direction, and is divided into $H \times W$ small sections of $1$ kilometer square. The $i$-th section from the north and $j$-th section from the west is denoted by $(i, j)$.

Each section either has a cloud in the sky above it or does not have a cloud. Every cloud moves $1$ kilometer east every $1$ minute. Since the weather is really nice today, no clouds will move into JOI City from outside JOI City.

Right now, it is known whether or not there is a cloud in the sky above each section. As a weather forecaster, you are to predict for each section how many minutes from now a cloud will come to the sky above that section for the first time.

For each section, find how many minutes from now a cloud will come to the sky above that section for the first time.

Input

The input consists of $1 + H$ lines.

The first line contains the integers $H, W$ ($1 \le H \le 100, 1 \le W \le 100$) separated by a space. This represents that JOI City is divided into $H \times W$ small sections of $1$ kilometer square.

The $i$-th line ($1 \le i \le H$) of the following $H$ lines contains a string of $W$ characters. The $j$-th character ($1 \le j \le W$) of the $W$ characters represents whether or not there is currently a cloud in the sky above section $(i, j)$. If there is a cloud, the character 'c' (lowercase English letter) is written, and if there is no cloud, the character '.' (period) is written.

Output

The output consists of $H$ lines, and each line consists of $W$ space-separated integers. The $j$-th integer on the $i$-th line of the output ($1 \le i \le H, 1 \le j \le W$) must represent how many minutes from now a cloud will come to the sky above section $(i, j)$ for the first time. However, if there is already a cloud in the sky above section $(i, j)$ right now, output $0$, and if no cloud will ever come to the sky above section $(i, j)$ no matter how many minutes pass, output $-1$.

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

Examples

Input 1

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

Output 1

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

Note

In Example 1, JOI City is divided into $3 \times 4$ sections. The current cloud situation in JOI City is as follows. The top of the figure represents north.

After this, every $1$ minute, the clouds move as follows.

Input 2

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

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