JOI deltar på en sosial sammenkomst under IOI. På sammenkomsten er smørbrød plassert langs et rutenett med $R$ rader og $C$ kolonner. Hvert smørbrød har form som en rettvinklet likebeint trekant der to sider er like lange som siden i en rutenettcelle, og hver celle inneholder to smørbrød plassert slik at hypotenusene deres berører hverandre. Figuren nedenfor viser et eksempel på hvordan smørbrødene er plassert.

Figur 1. Eksempel på plassering av smørbrød

Et smørbrød kan ikke tas hvis det oppfyller begge de følgende betingelsene: Hypotenusen berører et annet smørbrød som ennå ikke er tatt. Minst én av de to andre sidene utenom hypotenusen berører et annet smørbrød som ennå ikke er tatt.

Andre smørbrød enn disse kan tas.

Tilstanden der ingen smørbrød er tatt, er starttilstanden. For å ta et bestemt smørbrød fra starttilstanden kan det være nødvendig å ta andre smørbrød først. Avhengig av hvordan smørbrødene er plassert, kan det hende at noen smørbrød ikke kan tas i det hele tatt.

JOI ønsker å spise begge smørbrødene som ligger i samme celle. Han har ennå ikke bestemt seg for hvilken celles smørbrød han vil spise.

Han er interessert i det minste antallet smørbrød som må tas for å få tak i begge smørbrødene i en bestemt celle fra starttilstanden.

Oppgave

Gitt plasseringen av smørbrødene, avgjør for hver celle om det er mulig å ta begge smørbrødene i den cellen ved å ta noen smørbrød fra starttilstanden. Hvis det er mulig, finn det minste antallet smørbrød som må tas. Merk at antallet smørbrød skal inkludere de to målsmørbrødene selv.

Inndata

Les følgende data fra standard inndata: Den første linjen inneholder to heltall $R$ og $C$ adskilt med mellomrom. Disse representerer at smørbrødene er plassert langs et rutenett med $R$ rader og $C$ kolonner. Den $i$-te linjen ($1 \le i \le R$) av de påfølgende $R$ linjene inneholder en streng med lengde $C$. Hvert tegn er enten 'N' eller 'Z'. Det $j$-te tegnet ($1 \le j \le C$) i denne strengen representerer plasseringen av smørbrødene i cellen på den $i$-te raden ovenfra og $j$-te kolonnen fra venstre. 'N' og 'Z' representerer henholdsvis følgende plasseringer.

Figur 2. Plassering av smørbrød i hver celle

Utdata

Skriv ut $R$ linjer til standard utdata. Den $i$-te linjen ($1 \le i \le R$) skal inneholde $C$ heltall adskilt med mellomrom. Det $j$-te heltallet ($1 \le j \le C$) skal være det minste antallet smørbrød som må tas for å få tak i begge smørbrødene i cellen på den $i$-te raden ovenfra og $j$-te kolonnen fra venstre. Hvis det ikke er mulig å ta dem, skriv ut -1.

Begrensninger

Alle inndata oppfyller følgende betingelser: $1 \le R \le 400$ $1 \le C \le 400$

Deloppgaver

Deloppgave 1 [35 poeng]

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

Deloppgave 2 [65 poeng]

• Ingen ytterligere begrensninger.

Eksempler

Inndata 1

2 3
NZN
ZZN

Utdata 1

10 8 2
8 6 4

Forklaring 1

Plasseringen av smørbrød i Eksempel 1 tilsvarer Figur 1 i oppgavebeskrivelsen. For eksempel, for å ta de to smørbrødene i cellen på 2. rad ovenfra og 2. kolonne fra venstre, kan man ta smørbrødene i følgende rekkefølge: Ta det øverste høyre smørbrødet i cellen på 1. rad, 3. kolonne. Ta det nederste venstre smørbrødet i cellen på 1. rad, 3. kolonne. Ta det øverste høyre smørbrødet i cellen på 2. rad, 3. kolonne. Ta det nederste venstre smørbrødet i cellen på 2. rad, 3. kolonne. Ta det nederste høyre smørbrødet i cellen på 2. rad, 2. kolonne. Ta det øverste venstre smørbrødet i cellen på 2. rad, 2. kolonne.

Totalt tas 6 smørbrød, og siden dette er det minste antallet, skrives 6 ut.

Inndata 2

2 2
NZ
ZN

Utdata 2

-1 -1
-1 -1

Forklaring 2

I dette tilfellet kan ingen av smørbrødene tas.

Inndata 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