Conectate

Cerință

O matrice binară se numește conectată dacă se poate ajunge din orice valoare de $1$ în orice altă valoare de $1$ trecând doar prin valori de $1$. O matrice care conține doar $0$ se consideră conectată.

Se dă o matrice binară $C$ (nu neapărat conectată). Să se găsească două matrici binare conectate $A$ și $B$ astfel încât să se respecte următoarea condiție: $C_{ij}=1$ dacă și numai dacă $A_{ij} \neq B_{ij}$.

Se garantează că matricea $C$ conține cel puțin un $0$ pe fiecare rând.

Date de intrare

Pe prima linie se vor afla valorile $n$, $m$ (dimensiunile matricei). Următoarele $n$ linii conțin fiecare câte $m$ valori din mulțimea $\{0,1\}$, reprezentând elementele matricei $C$.

Date de ieșire

Dacă nu există soluție, se va afișa $-1$. Altfel, se va afișa matricea $A$ sub forma a $n$ linii conținând câte $m$ valori din mulțimea $\{0,1\}$, apoi se va afișa matricea $B$ în același mod. Între cele două matrici se poate afișa un rând liber, chiar dacă nu este necesar.

Restricții și precizări

Pentru toate testele, se respectă $1 \le n, m \le 1000$.

Exemplul 1

stdin

4 4
0 1 0 1
0 0 1 0
0 1 0 1
1 1 1 0

stdout

0 1 1 1
0 1 0 0
0 1 1 1
1 1 1 0

0 0 1 0
0 1 1 0
0 0 1 0
0 0 0 0

Explicație

Exemplul este ilustrat în imaginea de mai sus. În stânga-sus este reprezentată matricea $C$ (celulele marcate cu 'X' conțin $1$). Jos sunt reprezentate cele două matrici $A$ și $B$ (celulele colorate conțin $1$). În dreapta-sus este reprezentată suprapunerea celor două matrici $A$ și $B$. Se poate observa cum celulele marcate cu 'X' apar în exact una din matricile $A$ și $B$, conform cerinței.

Acasta nu este unica soluție.

Exemplul 2

stdin

1 9
0 1 1 0 0 1 1 1 0

stdout

0 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 1 0

Explicație

Rândul liber dintre cele două matrici este opțional.

Exemplul 3

stdin

1 9
0 1 1 0 1 0 1 1 0

stdout

-1

Explicație

În acest caz, nu există soluție.