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ă).

# Henry alege o mulţime $C{~i~}$ 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 $E{~i~}$ de bucăţi de ciocolată aşezate pe caroiaj şi le va elimina; apoi, ea va aşeza pe caroiaj o altă mulţime $A{~i~}$ 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

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.

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 $B{~i~}$ - numărul de celule blocate de Henry la pasul $i$. Pe următoarele $B{~i~}$ 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

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.

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 $X{~1~}$, $Y{~1~}$, $X{~2~}$, $Y{~2~}$ reprezentând coordonatele celulelor $(X{~1~}, Y{~1~})$ and $(X{~2~}, Y{~2~})$ 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.

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.

| Mulţimea A~0~ 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 E{~1~} = { ((2,1),(2,2)), ((1,3),(2,3)) } şi adăugăm mulţimea A{~1~} = { ((2,2),(2,3)) } la primul pas.
Eliminăm mulţimea E{~2~} = { ((1,1),(1,2)), ((2,2),(2,3)) } şi adăugăm mulţimea A{~2~} = { ((2,1),(2,2)) } la al doilea pas.

Pasul 3 nu poate fi efectuat aşa că afişăm -1. Ignorăm pasul 4.
|