JOI-kun uczestniczy w spotkaniu towarzyskim IOI. Na spotkaniu kanapki ułożono na siatce kwadratowych pól o $R$ wierszach i $C$ kolumnach. Kanapki mają kształt trójkątów prostokątnych równoramiennych, których dwa boki mają długość równą długości boku pola. Na każdym polu leżą dwie kanapki stykające się przeciwprostokątnymi. Poniższy rysunek przedstawia przykładowe ułożenie kanapek.

Rysunek 1. Przykładowe ułożenie kanapek.

Nie można zabrać kanapki, która jednocześnie spełnia oba poniższe warunki.

• Jej przeciwprostokątna styka się z inną kanapką, która nie została jeszcze zabrana.
• Co najmniej jeden z jej dwóch boków innych niż przeciwprostokątna styka się z inną kanapką, która nie została jeszcze zabrana.

Każdą inną kanapkę można zabrać.

Stan, w którym nie zabrano jeszcze żadnej kanapki, nazywamy stanem początkowym. Aby zabrać pewną kanapkę ze stanu początkowego, może być konieczne wcześniejsze zabranie kilku innych kanapek. W zależności od ułożenia mogą też istnieć kanapki, których nie da się zabrać.

JOI-kun chce zjeść obie kanapki leżące na jednym polu. Nie zdecydował jeszcze, z którego pola weźmie kanapki.

Zastanawia się, jaka jest najmniejsza liczba kanapek, które trzeba zabrać, aby ze stanu początkowego zabrać obie kanapki z pewnego pola.

Zadanie

Napisz program, który na podstawie ułożenia kanapek dla każdego pola stwierdzi, czy można zabrać obie leżące na nim kanapki, zabierając pewną liczbę kanapek ze stanu początkowego. Jeśli jest to możliwe, program ma obliczyć najmniejszą liczbę kanapek, które trzeba zabrać. Do tej liczby wliczamy również dwie docelowe kanapki.

Wejście

Wczytaj następujące dane ze standardowego wejścia.

• Pierwszy wiersz zawiera oddzielone spacją liczby całkowite $R,C$. Oznaczają one, że kanapki ułożono na siatce kwadratowych pól o $R$ wierszach i $C$ kolumnach.
• $i$-ty ($1\le i\le R$) z kolejnych $R$ wierszy zawiera napis złożony z $C$ znaków. Każdy znak to N lub Z. $j$-ty znak od lewej ($1\le j\le C$) opisuje ułożenie kanapek na polu w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej. Znaki N i Z oznaczają odpowiednio następujące ułożenia.

Rysunek 2. Ułożenie kanapek na poszczególnych polach.

Wyjście

Wypisz $R$ wierszy na standardowe wyjście. W $i$-tym wierszu ($1\le i\le R$) wypisz $C$ liczb całkowitych oddzielonych spacjami. Jako $j$-tą liczbę ($1\le j\le C$) wypisz najmniejszą liczbę kanapek, które trzeba zabrać, aby zabrać obie kanapki z pola w $i$-tym wierszu od góry i $j$-tej kolumnie od lewej. Jeśli jest to niemożliwe, wypisz $-1$.

Ograniczenia

Wszystkie dane wejściowe spełniają poniższe warunki.

• $1\le R\le 400$.
• $1\le C\le 400$.

Podzadania

Podzadanie 1 [35 punktów]

Spełnione są następujące warunki.

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

Podzadanie 2 [65 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

2 3
NZN
ZZN

Wyjście 1

10 8 2
8 6 4

Uwagi

Ułożenie kanapek w pierwszym przykładzie odpowiada rysunkowi 1 w treści zadania.

Na przykład, aby zabrać obie kanapki z pola w drugim wierszu od góry i drugiej kolumnie od lewej, można zabierać kanapki w następującej kolejności.

• Zabierz prawą górną kanapkę z pola w pierwszym wierszu od góry i trzeciej kolumnie od lewej.
• Zabierz lewą dolną kanapkę z pola w pierwszym wierszu od góry i trzeciej kolumnie od lewej.
• Zabierz prawą górną kanapkę z pola w drugim wierszu od góry i trzeciej kolumnie od lewej.
• Zabierz lewą dolną kanapkę z pola w drugim wierszu od góry i trzeciej kolumnie od lewej.
• Zabierz prawą dolną kanapkę z pola w drugim wierszu od góry i drugiej kolumnie od lewej.
• Zabierz lewą górną kanapkę z pola w drugim wierszu od góry i drugiej kolumnie od lewej.

Łącznie zabieramy 6 kanapek. Jest to najmniejsza możliwa liczba, więc wypisujemy $6$.

Wejście 2

2 2
NZ
ZN

Wyjście 2

-1 -1
-1 -1

Uwagi

W tym przypadku nie można zabrać żadnej kanapki.

Wejście 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Wyjście 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