inmultire

Cerință

Se dă $n$ și o matrice binară, numită $c$, cu $n$ linii și $n$ coloane. Aflați dacă există două șiruri binare $a$ și $b$ de lungime $n$ astfel încât $a_i \cdot b_j = c_{i,j}$ pentru fiecare $1 \leq i, j \leq n$. Dacă nu există două astfel de șiruri, afișați 1.

Date de intrare

Pe prima linie a fișierului de intrare inmultire.in se află numărul $n$. Pe următoarele $n$ linii se află câte $n$ elemente, reprezentând matricea $c$.

Date de ieșire

Să se afișeze -1 în fișierul inmultire.out dacă nu există soluție, altfel pe prima linie să se afișeze șirul $a$ și pe a doua linie să se afișeze șirul $b$. Dacă există mai multe soluții, se poate afișa oricare.

• $2 \leq n \leq 1 \ 000$
• $0 \leq c_{i, j} \leq 1$

Restricții și precizări

Exemplul 1

inmultire.in

2
0 0
1 1

inmultire.out

0 1
1 1

Explicație

La primul exemplu, avem $a = [0, 1]$ și $b = [1, 1]$. $c_{1, 1} = a_1 \cdot b_1 = 0$, $c_{1, 2} = a_1 \cdot b_2 = 0$, $c_{2, 1} = a_2 \cdot b_1 = 1$ și $c_{2, 2} = a_2 \cdot b_2 = 1$. Deci, soluția aceasta este bună.

Exemplul 2

inmultire.in

5
1 0 0 1 1
1 0 0 1 1
1 0 0 1 1
0 0 0 0 0
1 0 0 1 1

inmultire.out

1 1 1 0 1
1 0 0 1 1

Exemplul 3

inmultire.in

2
1 0 
0 1

inmultire.out

-1

Explicație

La al treilea exemplu, se poate demonstra că nu există soluție. Așadar, afisăm -1.