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:

• se află la marginea satului (pe linia 1, respectiv N sau pe coloana 1, respectiv M a matricei);
• 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 foc 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ța

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 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

Se vor afișa la ecran, 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 ≤ N, M ≤ 1000
• A[i][j] ∈ {0, 1}, 1 ≤ i ≤ N, 1 ≤ j ≤ M
• Se garantează că există cel puțin o casă care se află în pericol.
• Pentru 30 de puncte, 1 ≤ N, M ≤ 100

Exemplul 1:

Intrare

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

Ieșire

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

Explicație

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:

Intrare

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

Ieșire

-1

Explicație

În cazul celui de-al doilea exemplu, 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.