În anul de grație 6983 (1475), armata turcească condusă de Suleiman Pașa a fost învinsă de armatele aliate creștine moldo-maghiaro-polone conduse de Ștefan cel Mare. Bătălia a avut loc lângă Vaslui în locul numit Podu Înalt.

Terenul în care s-au desfășurat luptele poate fi reprezentat ca un tablou bidimensional cu N linii și M coloane, numerotate începând de la 1. Poziția unui element din matrice este identificată prin linia și coloana corespunzătoare. La luptă au participat P oșteni, în poziții distincte, pozițiile acestora în teren fiind cunoscute.

În tabloul bidimensional ce reprezintă terenul pot fi duse, sub un unghi de 45°, diagonale tactice care separă oștenii. O diagonală tactică trebuie să înceapă și să se termine pe o poziție situată pe marginea terenului (linia 1 sau linia N, respectiv coloana 1 sau coloana M). O diagonală tactică nu poate trece printr-o poziție în care se află un oștean.

Ștefan, mare strateg, își pune problema dacă există posibilitatea să separe oștenii în grupuri egale din punct de vedere numeric, trasând astfel de diagonale tactice.

Cerința

• Determinaţi o diagonală tactică astfel încât terenul de luptă să fie împărțit în două zone care conţin acelaşi număr de oșteni. Dacă nu există soluție, se va scrie doar valoarea -1.
• Determinaţi două diagonale tactice perpendiculare care împart terenul de luptă în patru zone care conţin, fiecare, acelaşi număr de oșteni. Dacă nu există soluție, se va scrie doar valoarea -1.

Date de intrare

Fișierul de intrare vaslui1475.in conține pe prima linie numerele naturale N, M și P, separate prin câte un spațiu, reprezentând numărul de linii, numărul de coloane, respectiv numărul de oșteni. Pe următoarele P linii sunt descrise pozițiile oștenilor, câte un oștean pe o linie. Linia care descrie poziția unui oștean conține două numere naturale lin și col, separate printr-un spațiu, reprezentând linia, respectiv coloana zonei de teren în care se află oșteanul respectiv.

Date de ieșire

Fișierul de ieșire vaslui1475.out va conține va conține două linii. Pe prima linie sunt scrise 4 numere naturale lin1, col1, lin2 și col2, separate prin câte un spațiu, reprezentând poziția primului element, respectiv poziția ultimului element de pe diagonala determinată la cerința 1. Dacă nu există soluție, va fi scrisă doar valoarea -1.

Pe cea de a doua linie sunt scrise 8 numere naturale lin11, col11, lin12, col12, lin21, col21, lin22 și col22, separate prin câte un spațiu, reprezentând poziția primului element și poziția ultimului element de pe prima diagonală, respectiv poziția primului element și poziția ultimului element de pe a doua diagonală determinate la cerința 2. Dacă nu există soluție, va fi scrisă doar valoarea -1.

Restricții și precizări

• 2 ≤ N, M ≤ 50.000
• 0 ≤ P ≤ min(M x N, 50.000)
• Liniile și coloanele matricei sunt numerotate începând cu 1.
• Primul element de pe o diagonală tactică este cel din stânga, ultimul este cel din dreapta.
• Dacă există mai multe soluții corecte se va afișa oricare dintre ele.
• Se va acorda punctaj parțial pentru rezolvarea corectă numai a cerinței 1. În acest caz, se vor acorda 40% din punctajul pe test.
• Pentru 70 de puncte, 2 ≤ N, M ≤ 200
• Pentru 30 de puncte, Nu există restricții adiționale

Exemplul 1:

vaslui1475.in

6 8 4
1 1
2 5
5 4
6 8

vaslui1475.out

6 2 1 7
6 2 1 7 1 2 6 7

Explicație

Exemplul 2:

vaslui1475.in

7 10 4
1 9
2 10
5 9
3 9

vaslui1475.out

1 8 3 10
-1

Explicație