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

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.

Luând o pauză de la curăţenie, Henry şi Hetty se joacă cu un caroiaj de dimensiuni $N * M$ şi multe 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 $A{~0~}$ 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:

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 $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.

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 marcate 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 marcate 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 $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.

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~})$ şi $(X{~2~}, Y{~2~})$ acoperite de bucata 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 $A{~0~}$ 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 $E{~i~}$ de bucăţi eliminate de Hetty, şi apoi mulţimea $A{~i~}$ de bucăţi 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.

În fişierul de ieşire $ciocolata2.out$ trebuie să afişaţi întâi mulţimea $A{~0~}$ de bucăţi de ciocolată 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 $E{~i~}$ de bucăţi eliminate de Hetty, şi apoi mulţimea $A{~i~}$ de bucăţi 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.

h2. Restricţii
* $1 ≤ N, M ≤ 70$
* $1 ≤ K ≤ 1700$

* Pentru $20%$ din teste, $1 ≤ N, M ≤ 10$.
* Pentru $50%$ din teste, $1 ≤ N, M ≤ 50$.

* Pentru $10%$ din teste, $1 ≤ N, M ≤ 10$.
* Pentru $40%$ din teste, $1 ≤ N, M ≤ 50$.

* Se garantează că pasul $0$ poate fi mereu efectuat.

* Se garantează că nicio celulă nu va fi blocată de două ori.

* Se garantează că nicio celulă nu va fi marcată de două ori.

* Coordonatele celulelor sunt indexate de la $1$.

h2. Afişare rapidă.

h2. Afişare rapidă

Deoarece fişierele de ieşire generate pot fi mari, se recomandă parsarea afişării. Pentru a vă fi de ajutor, vă oferim următorul cod:

    char m_buffer[kBufferSize];
    char digit_buffer[30];
    int m_pos;

} fout("ciocolata2.out;

} fout("ciocolata2.out");

==

Această clasă poate afişa doar *numere naturale pozitive* şi *şiruri de caractere*. Spre exemplu, pentru a afişa o pereche de numere separate prin spaţiu folosiţi:

Această clasă poate afişa doar *numere naturale nenegative* şi *şiruri de caractere*. Spre exemplu, pentru a afişa o pereche de numere separate prin spaţiu, respectiv numărul $-1$, folosiţi:

== code(cpp) |
fout << a << " " << b << "\n";

fout << "-1\n";

==
h2. Exemplu

1 1 1 2
2 2 2 3
1

2 1 2 2

1 2 2 2

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

La pasul 1 se blocheaza celulele (2,1) şi (1,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.
La pasul 2 se blocheaza celulele (1,1) şi (2,3). 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.
La pasul 3 se blocheaza celula (1,2). Nu există nicio variantă pentru a compune mulţimile E{~3~} si A{~3~} aşa că afişăm -1. Ignorăm pasul 4.

La pasul 1 se marcheaza celulele (2,1) şi (1,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.
La pasul 2 se marcheaza celulele (1,1) şi (2,3). Eliminăm mulţimea E{~2~} = { ((1,1),(1,2)), ((2,2),(2,3)) }
şi adăugăm mulţimea A{~2~} = { ((1,2),(2,2)) } la al doilea pas.
La pasul 3 se marcheaza celula (1,2). Nu există nicio variantă pentru a compune mulţimile E{~3~} si A{~3~}
aşa că afişăm -1. Ignorăm pasul 4.

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