La città di JOI ha la forma di un rettangolo di $H$ chilometri in direzione nord-sud e $W$ chilometri in direzione est-ovest, ed è suddivisa in $H \times W$ piccole sezioni quadrate di $1$ chilometro di lato. La $i$-esima sezione da nord e $j$-esima da ovest è indicata con $(i, j)$.

Ogni sezione ha una nuvola nel cielo sopra di essa oppure non ha alcuna nuvola. Tutte le nuvole si spostano di $1$ chilometro verso est ogni $1$ minuto. Poiché oggi il tempo è davvero bello, nessuna nuvola entrerà nella città di JOI dall'esterno.

In questo momento è noto per ogni sezione se ci sia o meno una nuvola sopra di essa. Come meteorologo, devi prevedere per ciascuna sezione tra quanti minuti a partire da ora arriverà per la prima volta una nuvola nel cielo sopra quella sezione.

Per ciascuna sezione, trova tra quanti minuti a partire da ora arriverà per la prima volta una nuvola sopra quella sezione.

Input

L'input è composto da $1 + H$ righe.

La prima riga contiene gli interi $H, W$ ($1 \le H \le 100, 1 \le W \le 100$) separati da uno spazio. Questo indica che la città di JOI è suddivisa in $H \times W$ piccole sezioni quadrate di $1$ chilometro di lato.

La $i$-esima riga ($1 \le i \le H$) delle successive $H$ righe contiene una stringa di $W$ caratteri. Il $j$-esimo carattere ($1 \le j \le W$) dei $W$ caratteri indica se in questo momento c'è una nuvola sopra la sezione $(i, j)$. Se c'è una nuvola è scritto il carattere 'c' (lettera minuscola inglese), mentre se non c'è alcuna nuvola è scritto il carattere '.' (punto).

Output

L'output è composto da $H$ righe, ciascuna formata da $W$ interi separati da spazi. Il $j$-esimo intero sulla $i$-esima riga dell'output ($1 \le i \le H, 1 \le j \le W$) deve rappresentare tra quanti minuti a partire da ora arriverà per la prima volta una nuvola sopra la sezione $(i, j)$. Tuttavia, se c'è già una nuvola sopra la sezione $(i, j)$ in questo momento, stampa $0$; se invece non arriverà mai alcuna nuvola sopra la sezione $(i, j)$ indipendentemente da quanti minuti passino, stampa $-1$.

Non inserire spazi superflui all'inizio o alla fine di ciascuna riga dell'output.

Esempi

Input 1

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

Output 1

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

Nota

Nell'Esempio 1, la città di JOI è suddivisa in $3 \times 4$ sezioni. La situazione attuale delle nuvole nella città di JOI è la seguente. La parte superiore della figura rappresenta il nord.

Dopo di ciò, ogni $1$ minuto, le nuvole si spostano come segue.

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