기상 예보사

문제

JOI 시는 남북 방향으로 H 킬로미터, 동서 방향으로 W 킬로미터인 직사각형 모양이며, 한 변이 1 킬로미터인 H × W 개의 작은 구획으로 나뉘어 있다. 북쪽에서 i 번째, 서쪽에서 j 번째 작은 구획을 (i, j) 로 나타낸다.

각 구획은 상공에 구름이 있거나 구름이 없거나 둘 중 하나이다. 모든 구름은 1 분이 지날 때마다 1 킬로미터씩 동쪽으로 이동한다. 오늘은 날씨가 정말 좋기 때문에, JOI 시 밖에서 JOI 시 안으로 구름이 이동해 오는 일은 없다.

지금 각 구획의 상공에 구름이 있는지 없는지를 알고 있다. 기상 예보사인 당신은 각 구획에 대해, 지금으로부터 몇 분 후에 처음으로 그 구획의 상공에 구름이 오는지를 예측하게 되었다.

각 구획에 대해, 지금으로부터 몇 분 후에 처음으로 그 구획의 상공에 구름이 오는지를 구하는 프로그램을 작성하시오.

입력

입력은 1 + H 개의 줄로 이루어진다.

첫째 줄에는 정수 H, W (1 ≦ H ≦ 100, 1 ≦ W ≦ 100) 가 공백으로 구분되어 주어진다. 이는 JOI 시가 한 변이 1 킬로미터인 H × W 개의 작은 구획으로 나뉘어 있음을 나타낸다.

이어지는 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 을 출력한다.

출력의 각 줄의 처음과 끝에는 불필요한 공백을 넣지 않는다.

예제 입력 1

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

예제 출력 1

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

예제 1 에서 JOI 시는 3 × 4 개의 작은 구획으로 나뉘어 있다. 지금 JOI 시의 구름 상황은 다음과 같다. 그림의 위쪽이 북쪽을 나타낸다.

그 후, 1 분마다 구름은 다음과 같이 이동한다.

예제 입력 2

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

예제 출력 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