7. Osvetlenie

Korporácia Svetelných Prístrojov konečne predstavila svoj nový produkt. Je ním systém osvetlenia, ktorý sa skladá zo žiaroviek usporiadaných do mriežky \(n\times m\) a ku každej žiarovke prislúcha jedno tlačidlo, ktoré ju má prepínať.

Keď už bola výroba v plnom prúde, zistili, že niekomu z Federácie Kazisvetov a Sabotérov sa podarilo prepísať ich schémy, a teda všetky vyrobené kusy obsahujú chybu. Konkrétne, keď prepnete niektorú žiarovku, prepnú sa aj všetky susedné žiarovky (za susedné považujeme \(4\) žiarovky, ktoré sú od nej hore, dole, napravo a naľavo). Čo spraviť so všetkými týmito vadnými kusmi? Začali ich predávať ako špeciálnu edíciu.

Po krátkom čase bol ich technical support zahltený požiadavkami typu: “Dá sa nejak zapnúť táto a hentá a tamtá a ešte tieto tu žiarovky?”. Samozrejme, nikto nemá čas tieto požiadavky riešiť, a preto potrebujú vašu pomoc.

Úloha

Na vstupe dostanete požadovaný stav, ktoré žiarovky majú byť zapnuté a ktoré vypnuté. Na začiatku sú všetky žiarovky vypnuté a vašou úlohou je zistiť, ktoré tlačidlá treba stlačiť, aby sa žiarovky dostali do požadovaného stavu.

Formát vstupu

Na prvom riadku dostanete dve celé čísla (\(1 \le n, m \le 30\)). Nasleduje \(n\) riadkov, ktoré popisujú mriežku žiaroviek. Každý z nich sa skladá z \(m\) čísel, ktoré môžu byť \(0\) alebo \(1\). \(0\) znamená, že daná žiarovka má byť vypnutá a \(1\) znamená, že daná žiarovka má byť zapnutá.

Formát výstupu

Ak riešenie neexistuje, vypíšte \(-1\).

Ak existuje, vypíšte \(n\) riadkov po \(m\) čísel. Vypíšte \(0\), ak tlačidlo, ktoré patrí žiarovke na danom mieste, nemá byť stlačené a \(1\), ak má byť stlačené.

Hodnotenie

Sú \(4\) sady vstupov. Platia v nich nasledovné obmedzenia: 1. \(n, m \le 10\) 2. \(n, m \le 20\) 3. \(n, m \le 30\), existuje vždy práve jedno riešenie 4. \(n, m \le 30\)

Príklady

Input:

3 3
1 1 1
1 1 1
1 1 1

Output:

1 0 1
0 1 0
1 0 1

Input:

3 2
0 1
0 0
1 1

Output:

-1