JOI tekur þátt í félagsviðburði á IOI. Á viðburðinum er samlokum raðað í grind með $R$ röðum og $C$ dálkum. Hver samloka er í laginu eins og rétthyrndur jafnarma þríhyrningur þar sem tvær hliðar eru jafnlangar hliðarlengd reits í grindinni, og í hverjum reit eru tvær samlokur lagðar þannig að langhliðar þeirra snertast. Myndin hér að neðan sýnir dæmi um uppröðun samlokanna.

Mynd 1. Dæmi um uppröðun samloka

Ekki er hægt að taka samloku ef hún uppfyllir bæði eftirfarandi skilyrði: Langhlið hennar snertir aðra samloku sem enn hefur ekki verið tekin. Að minnsta kosti önnur af hinum tveimur hliðum hennar (öðrum en langhliðinni) snertir aðra samloku sem enn hefur ekki verið tekin.

Aðrar samlokur en þessar er hægt að taka.

Ástandið þegar engar samlokur hafa verið teknar er upphafsástandið. Til að taka tiltekna samloku út frá upphafsástandinu gæti þurft að taka aðrar samlokur fyrst. Eftir því hvernig samlokunum er raðað gæti verið ómögulegt að taka sumar samlokur yfirhöfuð.

JOI vill borða báðar samlokurnar sem eru í sama reitnum. Hann hefur enn ekki ákveðið úr hvaða reit hann ætlar að borða samlokurnar.

Hann hefur áhuga á lágmarksfjölda samloka sem þarf að taka til að ná báðum samlokunum í tilteknum reit út frá upphafsástandinu.

Verkefni

Gefið er hvernig samlokunum er raðað. Ákvarðið fyrir hvern reit hvort hægt sé að taka báðar samlokurnar í þeim reit með því að taka einhverjar samlokur út frá upphafsástandinu. Ef það er hægt skal finna lágmarksfjölda samloka sem þarf að taka. Athugið að fjöldi samloka á að innihalda markmiðssamlokurnar tvær sjálfar.

Inntak

Lesið eftirfarandi gögn úr staðalinntaki: Fyrsta línan inniheldur tvær heiltölur $R$ og $C$ aðskildar með bili. Þær tákna að samlokunum sé raðað í grind með $R$ röðum og $C$ dálkum. Lína $i$ ($1 \le i \le R$) af næstu $R$ línum inniheldur streng af lengd $C$. Hver stafur er annaðhvort 'N' eða 'Z'. Stafur $j$ ($1 \le j \le C$) í þessum streng táknar uppröðun samlokanna í reitnum í $i$-tu röð að ofan og $j$-ta dálki frá vinstri. 'N' og 'Z' tákna eftirfarandi uppraðanir, í þessari röð.

Mynd 2. Uppröðun samloka í hverjum reit

Úttak

Skrifið út $R$ línur í staðalúttak. Lína $i$ ($1 \le i \le R$) á að innihalda $C$ heiltölur aðskildar með bilum. Heiltala $j$ ($1 \le j \le C$) á að vera lágmarksfjöldi samloka sem þarf að taka til að ná báðum samlokunum í reitnum í $i$-tu röð að ofan og $j$-ta dálki frá vinstri. Ef ekki er hægt að taka þær skal skrifa út -1.

Skilyrði

Öll inntaksgögn uppfylla eftirfarandi skilyrði: $1 \le R \le 400$ $1 \le C \le 400$

Undirverkefni

Undirverkefni 1 [35 stig]

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

Undirverkefni 2 [65 stig]

• Engin frekari skilyrði.

Dæmi

Inntak 1

2 3
NZN
ZZN

Úttak 1

10 8 2
8 6 4

Athugasemd 1

Uppröðun samlokanna í Dæmi 1 samsvarar Mynd 1 í verkefnislýsingunni. Til dæmis, til að taka samlokurnar tvær í reitnum í 2. röð að ofan og 2. dálki frá vinstri, er hægt að taka samlokurnar í eftirfarandi röð: Taka efri hægri samlokuna í reitnum í 1. röð, 3. dálki. Taka neðri vinstri samlokuna í reitnum í 1. röð, 3. dálki. Taka efri hægri samlokuna í reitnum í 2. röð, 3. dálki. Taka neðri vinstri samlokuna í reitnum í 2. röð, 3. dálki. Taka neðri hægri samlokuna í reitnum í 2. röð, 2. dálki. Taka efri vinstri samlokuna í reitnum í 2. röð, 2. dálki.

Alls eru teknar 6 samlokur, og þar sem þetta er lágmarkið er 6 skrifað út.

Inntak 2

2 2
NZ
ZN

Úttak 2

-1 -1
-1 -1

Athugasemd 2

Í þessu tilviki er ekki hægt að taka neina af samlokunum.

Inntak 3

5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZN

Úttak 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