JOI osallistuu IOI:n illanviettoon. Tilaisuudessa voileivät on aseteltu $R$ rivin ja $C$ sarakkeen ruudukkoon. Jokainen voileipä on tasakylkisen suorakulmaisen kolmion muotoinen siten, että sen kaksi kylkeä ovat yhtä pitkiä kuin ruudukon ruudun sivu, ja jokaisessa ruudussa on kaksi voileipää asetettuna niin, että niiden hypotenuusat koskettavat toisiaan. Alla oleva kuva esittää esimerkin voileipien asettelusta.

Kuva 1. Esimerkki voileipien asettelusta

Voileipää ei voi ottaa, jos se täyttää molemmat seuraavista ehdoista: Sen hypotenuusa koskettaa toista voileipää, jota ei ole vielä otettu. Ainakin toinen sen kahdesta muusta sivusta kuin hypotenuusasta koskettaa toista voileipää, jota ei ole vielä otettu.

Muut kuin tällaiset voileivät voidaan ottaa.

Tilaa, jossa yhtään voileipää ei ole vielä otettu, kutsutaan alkutilaksi. Tietyn voileivän ottaminen alkutilasta voi vaatia muiden voileipien ottamista ensin. Voileipien asettelusta riippuen joitakin voileipiä ei välttämättä voida ottaa lainkaan.

JOI haluaa syödä molemmat samassa ruudussa olevat voileivät. Hän ei ole vielä päättänyt, minkä ruudun voileivät hän syö.

Hän on kiinnostunut siitä, mikä on pienin määrä voileipiä, jotka on otettava alkutilasta lähtien, jotta saadaan tietyn ruudun molemmat voileivät.

Tehtävä

Kun voileipien asettelu annetaan, selvitä jokaiselle ruudulle, onko kyseisen ruudun molemmat voileivät mahdollista saada ottamalla joitakin voileipiä alkutilasta lähtien. Jos se on mahdollista, etsi pienin määrä voileipiä, jotka täytyy ottaa. Huomaa, että voileipien lukumäärään tulee laskea mukaan myös nuo kaksi tavoitteena olevaa voileipää.

Syöte

Lue seuraavat tiedot vakiosyötteestä: Ensimmäisellä rivillä on kaksi välilyönnillä erotettua kokonaislukua $R$ ja $C$. Nämä ilmaisevat, että voileivät on aseteltu $R$ rivin ja $C$ sarakkeen ruudukkoon. Seuraavien $R$ rivin $i$:nnellä rivillä ($1 \le i \le R$) on pituudeltaan $C$ oleva merkkijono. Jokainen merkki on joko 'N' tai 'Z'. Tämän merkkijonon $j$:s merkki ($1 \le j \le C$) ilmaisee voileipien asettelun ruudussa, joka sijaitsee $i$:nnellä rivillä ylhäältä ja $j$:nnessä sarakkeessa vasemmalta. 'N' ja 'Z' tarkoittavat vastaavasti seuraavia asetteluja.

Kuva 2. Voileipien asettelu kussakin ruudussa

Tuloste

Tulosta $R$ riviä vakiotulosteeseen. Rivillä $i$ ($1 \le i \le R$) tulee olla $C$ välilyönnein erotettua kokonaislukua. Luvun $j$ ($1 \le j \le C$) tulee olla pienin määrä voileipiä, jotka täytyy ottaa, jotta saadaan molemmat voileivät ruudusta, joka sijaitsee $i$:nnellä rivillä ylhäältä ja $j$:nnessä sarakkeessa vasemmalta. Jos niiden ottaminen ei ole mahdollista, tulosta -1.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot: $1 \le R \le 400$ $1 \le C \le 400$

Osatehtävät

Osatehtävä 1 [35 pistettä]

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

Osatehtävä 2 [65 pistettä]

• Ei lisärajoituksia.

Esimerkit

Syöte 1

2 3
NZN
ZZN

Tuloste 1

10 8 2
8 6 4

Huomautus 1

Esimerkin 1 voileipien asettelu vastaa tehtävänannon Kuvaa 1. Esimerkiksi saadakseen kaksi voileipää ruudusta, joka on 2. rivillä ylhäältä ja 2. sarakkeessa vasemmalta, voileivät voidaan ottaa seuraavassa järjestyksessä: Otetaan 1. rivin 3. sarakkeen ruudun oikean yläkulman voileipä. Otetaan 1. rivin 3. sarakkeen ruudun vasemman alakulman voileipä. Otetaan 2. rivin 3. sarakkeen ruudun oikean yläkulman voileipä. Otetaan 2. rivin 3. sarakkeen ruudun vasemman alakulman voileipä. Otetaan 2. rivin 2. sarakkeen ruudun oikean alakulman voileipä. Otetaan 2. rivin 2. sarakkeen ruudun vasemman yläkulman voileipä.

Yhteensä otetaan 6 voileipää, ja koska tämä on pienin mahdollinen määrä, tulostetaan 6.

Syöte 2

2 2
NZ
ZN

Tuloste 2

-1 -1
-1 -1

Huomautus 2

Tässä tapauksessa yhtäkään voileipää ei voida ottaa.

Syöte 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Tuloste 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