JOI nimmt an einem Empfang der IOI teil. Dort liegen Sandwiches auf einem Raster aus quadratischen Feldern mit $R$ Zeilen und $C$ Spalten. Jedes Sandwich hat die Form eines gleichschenkligen rechtwinkligen Dreiecks, dessen beide Katheten so lang wie eine Feldseite sind. Auf jedem Feld liegen zwei Sandwiches, deren Hypotenusen einander berühren. Die folgende Abbildung zeigt ein Beispiel für eine Anordnung.

Abbildung 1. Beispiel für eine Anordnung der Sandwiches

Ein Sandwich kann nicht genommen werden, wenn es gleichzeitig die folgenden beiden Bedingungen erfüllt:

• Seine Hypotenuse berührt ein anderes Sandwich, das noch nicht genommen wurde.
• Mindestens eine seiner beiden anderen Seiten berührt ein anderes Sandwich, das noch nicht genommen wurde.

Alle anderen Sandwiches können genommen werden.

Den Zustand, in dem noch kein Sandwich genommen wurde, nennen wir den Anfangszustand. Um ausgehend davon ein bestimmtes Sandwich zu nehmen, müssen möglicherweise zunächst einige andere Sandwiches genommen werden. Je nach Anordnung kann es auch Sandwiches geben, die überhaupt nicht genommen werden können.

JOI möchte beide Sandwiches essen, die auf demselben Feld liegen. Er hat noch nicht entschieden, von welchem Feld er die Sandwiches essen möchte.

Ihn interessiert die kleinste Anzahl an Sandwiches, die ausgehend vom Anfangszustand genommen werden müssen, um beide Sandwiches eines bestimmten Feldes zu nehmen.

Aufgabe

Schreibe ein Programm, das anhand der Anordnung der Sandwiches für jedes Feld bestimmt, ob beide Sandwiches dieses Feldes genommen werden können, indem ausgehend vom Anfangszustand einige Sandwiches genommen werden. Falls dies möglich ist, bestimme die kleinste Anzahl an Sandwiches, die dazu genommen werden müssen. Dabei werden die beiden gewünschten Sandwiches mitgezählt.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält die durch ein Leerzeichen getrennten ganzen Zahlen $R,C$. Sie bedeuten, dass die Sandwiches auf einem Raster aus quadratischen Feldern mit $R$ Zeilen und $C$ Spalten angeordnet sind.
• Die $i$-te ($1\le i\le R$) der folgenden $R$ Zeilen enthält eine Zeichenkette der Länge $C$. Jedes Zeichen ist N oder Z. Das $j$-te Zeichen von links ($1\le j\le C$) beschreibt die Anordnung der Sandwiches auf dem Feld in der $i$-ten Zeile von oben und der $j$-ten Spalte von links. N und Z stehen für die folgenden Anordnungen.

Abbildung 2. Anordnung der Sandwiches auf einem Feld

Ausgabe

Gib $R$ Zeilen auf der Standardausgabe aus. Die $i$-te Zeile ($1\le i\le R$) soll $C$ durch Leerzeichen getrennte ganze Zahlen enthalten. Gib als $j$-te Zahl ($1\le j\le C$) die kleinste Anzahl an Sandwiches aus, die genommen werden müssen, um beide Sandwiches auf dem Feld in der $i$-ten Zeile von oben und der $j$-ten Spalte von links zu nehmen. Falls dies unmöglich ist, gib $-1$ aus.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Teilaufgabe 1 [35 Punkte]

Die folgenden Bedingungen gelten.

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

Teilaufgabe 2 [65 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

2 3
NZN
ZZN

Ausgabe 1

10 8 2
8 6 4

Hinweis

Die Anordnung der Sandwiches in Beispiel 1 entspricht Abbildung 1 in der Aufgabenstellung.

Um beispielsweise beide Sandwiches des Feldes in der zweiten Zeile von oben und der zweiten Spalte von links zu nehmen, kann man die Sandwiches in der folgenden Reihenfolge nehmen:

• Nimm das Sandwich oben rechts auf dem Feld in der ersten Zeile von oben und der dritten Spalte von links.
• Nimm das Sandwich unten links auf dem Feld in der ersten Zeile von oben und der dritten Spalte von links.
• Nimm das Sandwich oben rechts auf dem Feld in der zweiten Zeile von oben und der dritten Spalte von links.
• Nimm das Sandwich unten links auf dem Feld in der zweiten Zeile von oben und der dritten Spalte von links.
• Nimm das Sandwich unten rechts auf dem Feld in der zweiten Zeile von oben und der zweiten Spalte von links.
• Nimm das Sandwich oben links auf dem Feld in der zweiten Zeile von oben und der zweiten Spalte von links.

Insgesamt werden 6 Sandwiches genommen. Da dies die kleinste mögliche Anzahl ist, wird $6$ ausgegeben.

Eingabe 2

2 2
NZ
ZN

Ausgabe 2

-1 -1
-1 -1

Hinweis

In diesem Fall kann kein einziges Sandwich genommen werden.

Eingabe 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Ausgabe 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