JOI 는 IOI 교류회에 참가하고 있다. 교류회에서는 $R$ 행 $C$ 열의 격자 모양으로 샌드위치가 배치되어 있다. 각 샌드위치는 빗변이 아닌 두 변의 길이가 격자 칸의 한 변의 길이와 같은 직각이등변삼각형 모양이며, 각 칸에는 두 개의 샌드위치가 서로 빗변이 맞닿도록 놓여 있다. 아래 그림은 샌드위치 배치의 한 예를 보여준다.

그림 1. 샌드위치 배치의 예

어떤 샌드위치가 다음 두 조건을 모두 만족하면 그 샌드위치는 가져갈 수 없다: 빗변이 아직 가져가지 않은 다른 샌드위치와 맞닿아 있다. 빗변이 아닌 두 변 중 적어도 하나가 아직 가져가지 않은 다른 샌드위치와 맞닿아 있다.

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

아무 샌드위치도 가져가지 않은 상태를 초기 상태라고 한다. 초기 상태에서 특정 샌드위치를 가져가기 위해서는 먼저 다른 샌드위치들을 가져가야 할 수도 있다. 샌드위치의 배치에 따라서는 아예 가져갈 수 없는 샌드위치가 있을 수도 있다.

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

그는 초기 상태에서 특정 칸에 있는 두 샌드위치를 모두 얻기 위해 가져가야 하는 샌드위치의 최소 개수에 관심이 있다.

과제

샌드위치의 배치가 주어질 때, 각 칸에 대하여 초기 상태에서 몇 개의 샌드위치를 가져감으로써 그 칸에 있는 두 샌드위치를 모두 가져갈 수 있는지 판별하라. 만약 가능하다면, 가져가야 하는 샌드위치의 최소 개수를 구하라. 단, 샌드위치의 개수에는 목표로 하는 두 샌드위치 자체도 포함해야 한다.

입력

표준 입력으로부터 다음 데이터를 읽어들인다: 첫째 줄에는 공백으로 구분된 두 정수 $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$ 번째 정수($1 \le j \le C$)는 위에서부터 $i$ 번째 행, 왼쪽에서부터 $j$ 번째 열에 있는 칸의 두 샌드위치를 모두 얻기 위해 가져가야 하는 샌드위치의 최소 개수여야 한다. 만약 가져가는 것이 불가능하다면 -1 을 출력하라.

제한

모든 입력 데이터는 다음 조건을 만족한다: $1 \le R \le 400$ $1 \le C \le 400$

서브태스크

서브태스크 1 [35점]

• $R \le 50$
• $C \le 50$

서브태스크 2 [65점]

• 추가적인 제한 조건이 없다.

예제

입력 1

2 3
NZN
ZZN

출력 1

10 8 2
8 6 4

노트 1

예제 1 의 샌드위치 배치는 문제 설명의 그림 1 에 해당한다. 예를 들어, 위에서부터 2 번째 행, 왼쪽에서부터 2 번째 열에 있는 칸의 두 샌드위치를 가져가기 위해서는 다음 순서대로 샌드위치를 가져가면 된다: 1 번째 행, 3 번째 열 칸의 오른쪽 위 샌드위치를 가져간다. 1 번째 행, 3 번째 열 칸의 왼쪽 아래 샌드위치를 가져간다. 2 번째 행, 3 번째 열 칸의 오른쪽 위 샌드위치를 가져간다. 2 번째 행, 3 번째 열 칸의 왼쪽 아래 샌드위치를 가져간다. 2 번째 행, 2 번째 열 칸의 오른쪽 아래 샌드위치를 가져간다. 2 번째 행, 2 번째 열 칸의 왼쪽 위 샌드위치를 가져간다.

총 6 개의 샌드위치를 가져가게 되며, 이것이 최소이므로 6 이 출력된다.

입력 2

2 2
NZ
ZN

출력 2

-1 -1
-1 -1

노트 2

이 경우, 어떤 샌드위치도 가져갈 수 없다.

입력 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

출력 3

10 12 14 16 2
8 -1 -1 -1 4
6 -1 -1 -1 6
4 -1 -1 -1 8
2 16 14 12 10