Á komandi ári 20XX verður Alþjóðlega upplýsingatæknihátíðin (International Omatsuri in Informatics) haldin í Japan. Í tengslum við undirbúning hátíðarinnar var þér falið að hanna merki (lógó) fyrir hana.

Merki Alþjóðlegu upplýsingatæknihátíðarinnar er í hvert sinn búið til út frá ákveðinni fastri grunnmynd. Þessi mynd samanstendur af nokkrum reitum sem valdir eru úr rétthyrndu neti ferningslaga reita sem er $W$ reitir á breiddina og $H$ reitir á hæðina. Að þessu sinni ákvaðst þú að lita þessa mynd í litum japanska þjóðfánans, rauðum og hvítum, til að gera hana að merki hátíðarinnar. Til að flækja ekki litunarvinnuna má aðeins nota $1$ lit á $1$ reit.

Til að ákveða hvernig best væri að skipta litunum leitaðir þú ráða hjá kunningja þínum sem er hönnuður. Samkvæmt frábæru fagurfræðilegu innsæi hans er æskilegt að bæði svæðið sem litað er rautt og svæðið sem litað er hvítt myndi línusamhverf form. Auk þess, með hliðsjón af litajafnvægi, sagði hann þér einnig að fjöldi reita sem litaðir eru rauðir ætti að vera $K$. Þar sem hann sagði þér ekki frá neinni litun sem uppfyllir þessi skilyrði þarft þú að finna slíka litun sjálf(ur). Gefin er myndin og gildið á $K$; skrifaðu forrit sem finnur $1$ litun sem uppfyllir skilyrðin.

Inntak

Í línu $1$ eru $3$ heiltölur $W, H, K$ ($1 \le W \le 40$, $1 \le H \le 40$, $1 \le K \le WH - 1$) aðskildar með bilum. Þær tákna breidd og hæð gefnu myndarinnar ásamt fjölda reita sem á að lita rauða.

Næstu $H$ línur lýsa gögnum myndarinnar. Í línu $i + 1$ ($1 \le i \le H$) eru $W$ tölur, hver um sig $0$ eða $1$, aðskildar með bilum. Þegar $j$-ta heiltalan ($1 \le j \le W$) í línu $i + 1$ er $1$ þýðir það að reiturinn í $i$-tu röð að ofan og $j$-ta dálki frá vinstri er notaður í myndinni; þegar hún er $0$ þýðir það að sá reitur er ekki notaður í myndinni. Í myndinni eru alltaf notaðir að minnsta kosti $2$ reitir. Tryggt er að gildið á $K$ sé strangt minna en fjöldi reita sem notaðir eru í myndinni.

Fyrir hvert inntak sem notað er við yfirferð er til að minnsta kosti $1$ litun sem uppfyllir skilyrðin.

Úttak

Skrifa skal úttakið á staðalúttak. Prentið heiltölur sem lýsa lituninni, $W$ heiltölur aðskildar með bilum í hverri línu yfir $H$ línur. Þegar $j$-ta heiltalan í línu $i$ er $1$ táknar það að reiturinn í $i$-tu röð að ofan og $j$-ta dálki frá vinstri sé litaður rauður; þegar hún er $2$ táknar það að sá reitur sé litaður hvítur. Fyrir reiti sem ekki eru notaðir í myndinni skal prenta $0$.

Ef margar litanir eru mögulegar má prenta hverja sem er þeirra.

Matsreglur

Meðal þeirra gagna sem notuð eru við yfirferð gildir $W, H \le 5$ fyrir $20\%$ stiganna.

Dæmi um inntak 1

4 3 2
0 1 0 0
1 0 1 1
1 0 0 0

Dæmi um úttak 1

0 2 0 0
1 0 2 1
2 0 0 0

Þetta úttak samsvarar eftirfarandi litun. Gráir reitir tákna reiti sem litaðir eru rauðir og hvítir reitir tákna reiti sem litaðir eru hvítir. Brotalínan og punktalínan eru samhverfuásar rauða svæðisins annars vegar og hvíta svæðisins hins vegar.

Eftirfarandi litanir uppfylla ekki skilyrðin: