JOI deltar i en social sammankomst under IOI. På sammankomsten är smörgåsar utplacerade i ett rutnät med $R$ rader och $C$ kolumner. Varje smörgås har formen av en rätvinklig likbent triangel där två sidor har samma längd som sidan i en rutnätscell, och varje cell innehåller två smörgåsar placerade så att deras hypotenuser vidrör varandra. Figuren nedan visar ett exempel på hur smörgåsarna kan vara placerade.

Figur 1. Exempel på placering av smörgåsar

En smörgås kan inte tas om den uppfyller båda följande villkor: Dess hypotenusa vidrör en annan smörgås som ännu inte har tagits. Minst en av dess två andra sidor utöver hypotenusan vidrör en annan smörgås som ännu inte har tagits.

Andra smörgåsar än dessa kan tas.

Tillståndet där inga smörgåsar har tagits är starttillståndet. För att ta en viss smörgås från starttillståndet kan det vara nödvändigt att först ta andra smörgåsar. Beroende på hur smörgåsarna är placerade kan det hända att vissa smörgåsar inte går att ta överhuvudtaget.

JOI vill äta båda smörgåsarna som ligger i samma cell. Han har ännu inte bestämt sig för vilken cells smörgåsar han ska äta.

Han är intresserad av det minsta antalet smörgåsar som måste tas för att få båda smörgåsarna i en viss cell från starttillståndet.

Uppgift

Givet placeringen av smörgåsarna, avgör för varje cell om det är möjligt att ta båda smörgåsarna i den cellen genom att ta några smörgåsar från starttillståndet. Om det är möjligt, bestäm det minsta antalet smörgåsar som behöver tas. Observera att antalet smörgåsar ska inkludera de två målsmörgåsarna själva.

Indata

Läs följande data från standard inmatning: Den första raden innehåller två mellanslagsseparerade heltal $R$ och $C$. Dessa anger att smörgåsarna är placerade i ett rutnät med $R$ rader och $C$ kolumner. Den $i$-te raden ($1 \le i \le R$) av de följande $R$ raderna innehåller en sträng av längd $C$. Varje tecken är antingen 'N' eller 'Z'. Det $j$-te tecknet ($1 \le j \le C$) i denna sträng anger placeringen av smörgåsarna i cellen på den $i$-te raden uppifrån och den $j$-te kolumnen från vänster. 'N' och 'Z' representerar följande placeringar.

Figur 2. Placering av smörgåsar i varje cell

Utdata

Skriv ut $R$ rader till standard utmatning. Den $i$-te raden ($1 \le i \le R$) ska innehålla $C$ mellanslagsseparerade heltal. Det $j$-te heltalet ($1 \le j \le C$) ska vara det minsta antalet smörgåsar som behöver tas för att få båda smörgåsarna i cellen på den $i$-te raden uppifrån och den $j$-te kolumnen från vänster. Om det inte är möjligt att ta dem, skriv ut -1.

Begränsningar

All indata uppfyller följande villkor: $1 \le R \le 400$ $1 \le C \le 400$

Deluppgifter

Deluppgift 1 [35 poäng]

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

Deluppgift 2 [65 poäng]

• Inga ytterligare begränsningar.

Exempel

Indata 1

2 3
NZN
ZZN

Utdata 1

10 8 2
8 6 4

Förklaring 1

Placeringen av smörgåsarna i Exempel 1 motsvarar Figur 1 i problembeskrivningen. För att till exempel ta de två smörgåsarna i cellen på 2:a raden uppifrån och 2:a kolumnen från vänster kan man ta smörgåsarna i följande ordning: Ta den övre högra smörgåsen i cellen på 1:a raden, 3:e kolumnen. Ta den nedre vänstra smörgåsen i cellen på 1:a raden, 3:e kolumnen. Ta den övre högra smörgåsen i cellen på 2:a raden, 3:e kolumnen. Ta den nedre vänstra smörgåsen i cellen på 2:a raden, 3:e kolumnen. Ta den nedre högra smörgåsen i cellen på 2:a raden, 2:a kolumnen. Ta den övre vänstra smörgåsen i cellen på 2:a raden, 2:a kolumnen.

Totalt tas 6 smörgåsar, och eftersom detta är det minsta möjliga antalet skrivs 6 ut.

Indata 2

2 2
NZ
ZN

Utdata 2

-1 -1
-1 -1

Förklaring 2

I detta fall kan ingen av smörgåsarna tas.

Indata 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Utdata 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