Luând o pauză de la curăţenie, Henry şi Hetty se joacă cu un caroiaj de dimensiuni $N * M$ şi o mulţime de bucăţi de ciocolată de dimensiuni $2 * 1$. Fiecare bucată de ciocolată poate fi plasată oriunde în caroiaj cât timp acoperă exact două celule. Bucăţile de ciocolată pot fi plasate atât vertical cât şi orizontal, şi nu trebuie să se suprapună cu alte bucăţi. O celulă se consideră acoperită dacă există o bucată de ciocolată plasată deasupra ei.

Henry şi Hetty vor executa $K+1$ paşi. La pasul 0, Henry o roagă pe Hetty să aşeze o mulţime $A0$ bucăţi de ciocolată în caroiaj astfel încât să acopere toate celulele. Apoi, paşii de la $1$ la $K$ constau în următoarele etape:

Henry şi Hetty vor executa $K+1$ paşi. La pasul $0$, Henry o roagă pe Hetty să aşeze o mulţime $A0$ bucăţi de ciocolată în caroiaj astfel încât să acopere toate celulele. Apoi, paşii de la $1$ la $K$ constau în următoarele etape:

# Henry alege o mulţime $Ci$ de celule nemarcate şi le marchează. Odată ce o celulă este marcată, ea rămâne astfel pentru toţi paşii ce vor urma.
# Hetty trebuie acum să se asigure că toate celulele marcate sunt descoperite, şi toate celulele nemarcate sunt acoperite. Pentru a face acest lucru, ea va alege o mulţime $Ei$ de bucăţi de ciocolată aşezate pe caroiaj şi le va elimina; apoi, ea va aşeza pe caroiaj o altă mulţime $Ai$ de bucăţi de ciocolată (posibil vidă).
Ajutaţi-o pe Hetty să facă paşii necesari: dacă reuşeşte să îi execute corect, poate mânca toată ciocolata folosită pentru joc!

h2. Date de intrare

Fişierul de intrare $ciocolata2.in$ ...

Pe prima linie a fişierului de intrare $ciocolata2.in$ se vor afla trei numere naturale $N$, $M$ şi $K$, cu semnificaţia din enunţ. Următoarele linii descriu paşii de la $1$ la $K$: pe prima linie ce descrie pasul $i$ se va afla un număr natural $Bi$ - numărul de celule blocate de Henry la pasul $i$. Pe următoarele $Bi$ linii se vor afla perechi de numere naturale $X$ şi $Y$, reprezentând coordonatele celulelor blocate de Henry la pasul curent.

h2. Date de ieşire

În fişierul de ieşire $ciocolata2.out$ ...

O mulţime de bucăţi de ciocolată este afişată în felul următor: pe prima linie, afişaţi un număr natural $P$, reprezentând dimensiunea mulţimii. Apoi, pe următoarele $P$ linii, afişaţi patru numere naturale X1, Y1, X2, Y2 reprezentând coordonatele celulelor (X1, Y1) and (X2, Y2) acoperite de piesa curentă. Atenţie: aceste celule trebuie să fie adiacente.
 
În fişierul de ieşire $ciocolata2.out$ trebuie să afişaţi întâi mulţimea de piese $A0$ adăugate de Hetty la pasul $0$. Apoi, pentru fiecare pas $i$ din cei $K$ rămaşi, trebuie să afişaţi întâi mulţimea de piese $Ei$ eliminate de Hetty, şi apoi mulţimea de piese $Ai$ adăugate de Hetty, în această ordine. Dacă nu este posibil ca Hetty să execute pasul $i$, afişaţi -1 şi terminaţi execuţia programului, ignorând paşii rămaşi din joc.

h2. Restricţii

h2. Exemplu

table(example). |_. ciocolata2.in |_. ciocolata2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

table(example). |_. ciocolata2.in |_. ciocolata2.out |_. Explicaţie |
| 2 3 4
2
2 1
1 3
2
1 1
2 3
1
1 2
1
2 2
| 3
1 1 1 2
2 1 2 2
1 3 2 3
2
2 1 2 2
1 3 2 3
1
2 2 2 3
2
1 1 1 2
2 2 2 3
1
2 1 2 2
-1
| Mulţimea A0 adăugată iniţial este formată din bucăţile ((1,1),(1,2)), ((2,1),(2,2)), ((1,3),(2,3)).
Eliminăm mulţimea E1 = ((2,1),(2,2)), ((1,3),(2,3)) şi adăugăm mulţimea A1 ((2,2),(2,3)) la primul pas.
Eliminăm mulţimea E2 = ((1,1),(1,2)), ((2,2),(2,3)) şi adăugăm mulţimea A2 ((2,1),(2,2)) la al doilea pas.
Pasul 3 nu poate fi efectuat aşa că afişăm -1. Ignorăm pasul 4.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="ciocolata2") ==