No.38 気象予報士 (Weather Forecaster)

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

JOI 市は南北方向に H キロメートル，東西方向に W キロメートルの長方形の形をしており，H × W 個の 1 キロメートル四方の小区画に区切られている．北から i 番目，西から j 番目の小区画を (i, j) と表す．

各小区画は上空に雲があるか雲がないかのどちらかである．すべての雲は，1 分経つごとに 1 キロメートル東に移動する．今日は実に天気が良いため，JOI 市の外から JOI 市内に雲が移動してくることはない．

今，各小区画の上空に雲があるかないかがわかっている．気象予報士であるあなたは，各小区画について，今から何分後に初めてその小区画の上空に雲が来るかを予測することになった．

各小区画について，今から何分後に初めてその小区画の上空に雲が来るか求めよ．

入力

入力は 1 + H 行からなる．

1 行目には，整数 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) が空白を区切りとして書かれている．これは，JOI 市が H × W 個の 1 キロメートル四方の小区画に区切られていることを表す．

続く H 行のうちの i 行目 (1 ≦ i ≦ H) には W 文字からなる文字列が書かれている．W 文字のうちの j 文字目 (1 ≦ j ≦ W) は，小区画 (i, j) の上空に，今，雲があるかどうかを表す．雲がある場合は文字 'c' (英小文字) が，雲がない場合は文字 '.' (ピリオド) が書かれている．

出力

出力は H 行からなり，それぞれの行は空白を区切りとした W 個の整数からなる．出力の i 行目の j 番目の整数 (1 ≦ i ≦ H, 1 ≦ j ≦ W) は，今から何分後に初めて小区画 (i, j) の上空に雲が来るかを表さなければならない．ただし，今すでに小区画 (i, j) の上空に雲がある場合は 0 を，何分経っても小区画 (i, j) の上空に雲が来ない場合は -1 を出力せよ．

出力の各行の行頭と行末には余計な空白を入れないこと．

入出力例

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

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

入出力例 1 では，JOI 市は 3 × 4 個の小区画に区切られている．今の JOI 市の雲の状況は以下の通りである．図の上が北を表す．

この後，1 分ごとに雲は以下のように移動する．

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

-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