샌드위치

JOI 군은 IOI 친목 모임에 참가하고 있다. 모임에서는 샌드위치가 세로 $R$행, 가로 $C$열의 정사각형 칸에 맞춰 놓여 있었다. 샌드위치는 두 변의 길이가 칸의 한 변과 같은 직각이등변삼각형 모양이고, 각 칸에는 샌드위치 2개가 빗변이 맞닿도록 놓여 있다.

아래 그림은 샌드위치 배치의 예이다.

그림 1. 샌드위치 배치 예

다음 두 조건을 동시에 만족하는 샌드위치는 가져갈 수 없다.

• 빗변이 아직 가져가지 않은 다른 샌드위치에 닿아 있다.
• 빗변이 아닌 두 변 중 적어도 하나가 아직 가져가지 않은 다른 샌드위치에 닿아 있다.

이 외의 샌드위치는 가져갈 수 있다.

샌드위치를 하나도 가져가지 않은 상태를 초기 상태라고 한다. 초기 상태에서 어떤 샌드위치를 가져가려면 다른 샌드위치를 먼저 가져가야 할 수도 있다. 배치에 따라서는 아무리 해도 가져갈 수 없는 샌드위치도 있다.

JOI 군은 같은 칸에 놓인 샌드위치 2개를 모두 먹고 싶어 한다. 어느 칸의 샌드위치를 먹을지는 아직 정하지 않았다.

초기 상태에서 어느 칸의 샌드위치 2개를 모두 가져갈 때, 가져가야 하는 샌드위치 개수의 최솟값이 궁금하다.

샌드위치 배치가 주어졌을 때, 각 칸에 대해 초기 상태에서 다른 샌드위치를 가져가는 방법으로 그 칸의 샌드위치 2개를 모두 가져갈 수 있는지 판정하라. 가져갈 수 있다면 가져가야 하는 샌드위치 개수의 최솟값을 구하라. 샌드위치 개수에는 목표인 샌드위치 2개도 포함한다.

표준 입력에서 다음 데이터를 읽어라.

• 첫 줄에 정수 $R$, $C$가 공백으로 구분되어 주어진다. 샌드위치가 세로 $R$행, 가로 $C$열의 정사각형 칸에 놓여 있음을 뜻한다.
• 이어지는 $R$줄 중 $i$번째 줄($1 \le i \le R$)에는 $C$개의 문자로 이루어진 문자열이 주어진다. 각 문자는 'N' 또는 'Z'이다. 이 문자열의 왼쪽에서 $j$번째 문자($1 \le j \le C$)는 위에서 $i$행, 왼쪽에서 $j$열 칸의 샌드위치 배치를 나타낸다. 'N'과 'Z'는 각각 아래 그림의 배치이다.

그림 2. 각 칸의 샌드위치 배치

표준 출력에 $R$줄을 출력하라. $i$번째 줄($1 \le i \le R$)에는 $C$개의 정수를 공백으로 구분하여 출력한다. $j$번째 정수는 위에서 $i$행, 왼쪽에서 $j$열 칸의 샌드위치 2개를 모두 가져갈 때 가져가야 하는 샌드위치 개수의 최솟값이다. 가져갈 수 없으면 $-1$을 출력하라.

$1 \le R \le 400$

$1 \le C \le 400$