Ilie Paduraru isi face testamentul. El are doi baieti si doua fete, iar ca avere un petec de padure. Ilie doreste sa imparta averea astfel incat sa nu nedreptateasca nici un copil. De aceea el a facut o harta dreptunghiulara care reprezinta petecul lui de padure si a marcat cu un cerculet fiecare copac. Harta lui Ilie poate fi reprezentata sub forma unui tablou bidimensional de dimensiuni NxM ca în figura a), fiecare dintre cei P copaci fiind reprezentat printr-un l. Dorinta lui Ilie este sa poata construi garduri care sa poata traversa padurea in diagonala, sub un unghi de 45°, astfel incat fiecare zona delimitata de garduri sa contina acelasi numar de copaci (figurile b) si c)).

Cerinta
a. Determinati extremitatile unui gard care împarte padurea în doua zone care contin acelasi numar de copaci (b))
b. Determinati extremitatile a doua gaduri perpendiculare care împart padurea în patru zone care contin acelasi numar de copaci (c)).

Date de intrare
Fisierul de intrare copaci.in contine pe prima linie 3 numere naturale N M P, separate prin cate un spatiu, reprezentand N - numarul de linii ale tabloului care reprezinta padurea, M - numarul de coloane, iar P - numarul de copaci din padure. Pe fiecare dintre urmatoarele P linii se afla cate doua numere naturale separate printr-un spatiu x y, reprezentand pozitiile celor P copaci (x este indicele liniei, iar y este indicele coloanei). Liniile sunt numerotate de la 1 la N, iar coloanele sunt numerotate de la 1 la M.

Date de iesire
Fisierul de iesire copaci.out va contine doua linii. Pe prima linie vor fi scrise 4 numere naturale separate prin cate un spatiu x1 y1 x2 y2, unde (x1,y1) si (x2,y2) reprezinta extremitatile gardului de la cerinta a.
Pe cea de a doua linie se afla 8 numere naturale separate prin cate un spatiu x3 y3 x4 y4 x5 y5 x6 y6, unde (x3,y3), (x4,y4) reprezinta extremitatile primului gard, iar (x5,y5), (x6,y6) reprezinta extremitatile celui de al doilea gard (perpendicular pe primul), garduri care reprezinta solutia cerintei b.
Pentru fiecare extremitate se specifica in primul rand indicele de linie (x), iar apoi indicele de coloana (y). Daca la una dintre cerinte nu exista solutie, pe linia corespunzatoare se va scrie doar valoarea -1.

Restrictii

• 2 <= N, M <= 200
• 0 <= P <= N*M
• Extremitatile gardurilor se afla intotdeauna la marginea padurii (linia 1, linia N, coloana 1 sau coloana M), in centrul patratului de plecare.
• Gardurile nu trebuie sa intersecteze nici un copac.

Exemple

Timp maxim de executie/test: 0.5 secunde

prof. Serban Marinel
Liceul de Informatica "Gr. C. Moisil" Iasi
marinel_serban@yahoo.com