foc

Satul Binăreni se află în pericol în urma incendiilor provocate în ultima lună. Acesta este reprezentat printr-o matrice binară cu $N$ linii și $M$ coloane. Toate celulele care au luat foc sunt reprezentate prin valoarea $0$. Toate celulele în care nu este produs un incendiu, reprezentate prin valori de $1$, conțin, inițial, câte o casă a unui sătean.

O celulă este considerată "safe" dacă nu a luat foc și se află într-una din cele două situații de mai jos:

1. se află la marginea satului (pe linia $1$, respectiv $N$ sau pe coloana $1$, respectiv $M$ a matricei);
2. cel puțin una din cele $4$ celule vecine pe direcțiile $N$, $V$, $S$ și $E$ sunt "safe".

Gosu, cel mai renumit pompier din sat, își dorește să salveze toate casele care nu se află în celule "safe", folosindu-și superputerea: acesta poate stinge o singură dată focul din toate celulele care au luat foc pe o linie $x$ și toate celulele care au luat for pe o coloană $y$, plasându-se la intersecția acestora, în celula $(x, y)$. Acesta se poate plasa atât pe o celulă cu incendiu, cât și pe o celulă care conține o casă. Astfel, după utilizarea superputerii sale, toate elementele de pe linia $x$, respectiv elementele de pe coloana $y$ vor căpăta valoarea $1$.

Cerință

Având în vedere că Gosu își poate folosi superputerea o singură dată, aflați toate perechile de coordonate $(x, y)$ posibile pe care se poate plasa acesta, astfel încât să salveze toate casele care sunt în pericol.

Date de intrare

Pe prima linie a intrării se găsesc două numere întregi $N$ și $M$, separate printr-un spațiu, reprezentând dimensiunile matricei.
Pe următoarele $N$ linii se află câte $M$ valori de $0$ sau $1$, separate prin spații, reprezentând descrierea matricei satului.

Date de ieșire

În consolă se vor afișa, pe linii diferite și separate printr-un spațiu, coordonatele celulelor pe care se poate plasa Gosu pentru a salva toate casele. Perechile de coordonate vor fi afișate în ordine lexicografică. Dacă nu există o soluție, se va afișa $-1$.

Restricții și precizări

• $3 \leq N, M \leq 10^3$;
• $A_{i,j} \in \{0,1\}, 1 \leq i \leq N, 1 \leq j \leq M$;
• Se garantează că există cel puțin o casă care se află în pericol;
• Pentru 30 de puncte, $1 \leq N, M \leq 100$.

Exemplul 1

stdin

7 8
0 0 0 0 1 1 0 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0

stdout

5 1
5 2
5 3
6 1
6 2
6 3
7 3

Explicație

În primul exemplu, satul este alcătuit din $9$ case, dintre care doar $6$ sunt ”safe”. Casele aflate în pericol sunt situate pe celulele $(2, 2)$, $(5, 4)$, respectiv $(6, 7)$. Soluția conține $7$ perechi de coordonate, afișate în ordine lexicografică. Dacă alege, spre exemplu, celula $(5, 1)$, Gosu va stinge focul în:

• celula vecină din $V$ a casei din celula $(2, 2)$;
• celulele vecine din $V$, respectiv $E$ ale casei situate pe $(5, 4)$;
• celula vecină din $N$ a ultimei case.

Toți acești vecini devin, la rândul lor, ”safe”.
Pe linia $7$ există o singură celulă din care Gosu poate stinge focul în cel puțin una din celulele vecine ale fiecărei case aflate în pericol: $(7, 3)$. După folosirea superputerii sale din această celulă, matricea devine:

Exemplul 2

stdin

9 9
0 0 0 0 0 0 1 0 1
0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0

stdout

-1

Explicație

Există $3$ case aflate în pericol, în celulele $(2, 2)$, $(5, 5)$, respectiv $(8, 8)$. Nu există nicio pereche de coordonate pe care Gosu se poate plasa, astfel încât să salveze toate cele $3$ case.