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