vaslui1475

Î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 ^{\circ}$, 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țe

• 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 două linii.

Pe prima linie sunt scrise $4$ numere naturale $lin_1$, $col_1$, $lin_2$ și $col_2$, 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 $lin_{11}$, $col_{11}$, $lin_{12}$, $col_{12}$, $lin_{21}$, $col_{21}$, $lin_{22}$ și $col_{22}$, 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 \leq N, M \leq 50 \ 000$
• $0 \leq P \leq min(M \cdot 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 teste în valoare de $70$ de puncte, $2 \leq N, M \leq 200$.

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