origami

Costel este pasionat de arta orientală a confecţionării obiectelor de hârtie, origami, dar este abia la început şi trebuie să se familiarizeze cu operaţiile de îndoire corectă a hârtiei. El are la dispoziţie o foaie de hârtie pătrată, ruptă dintr-un caiet de matematică, având dimensiunea de exact $N \cdot N$ pătrăţele. Îndoiturile trebuie realizate exact pe o linie orizontală sau verticală.

Sunt permise două tipuri de îndoituri:

• îndoitura de tipul $1$, îndoitură verticală executată la $X$ pătrăţele faţă de marginea stângă a foii: partea din stânga a foii se pliază către dreapta, de-a lungul liniei verticale aflate la distanţa de $X$ pătrăţele faţă de marginea stângă
• îndoitura de tipul $2$, îndoitură orizontală executată la $X$ pătrăţele faţă de marginea superioară a foii: partea de sus a foii se pliază în jos, de-a lungul liniei aflate la distanţa de $X$ pătrăţele faţă de marginea de sus a hârtiei.

În urma realizării unei succesiuni de îndoituri, din foaia iniţială de hârtie se va obţine un obiect, care va avea o formă dreptunghiulară, cu înălţimea $H$, lăţimea $M$ şi având grosimea egală cu numărul maxim de foi care se suprapun în cadrul obiectului obţinut.

Cerință

Dată fiind o succesiune de îndoituri aplicată unei foi de dimensiune $N \cdot N$, scrieţi un program care să determine înălţimea, lăţimea şi grosimea obiectului obţinut.

Date de intrare

Fişierul de intrare origami.in are următoarea structură :

• prima linie a fişierului conţine un număr natural $N$, reprezentând dimensiunea iniţială a hârtiei
• a doua linie conţine un număr natural $K$, reprezentând numărul îndoiturilor
• pe următoarele $K$ linii se găsesc perechi de numere naturale nenule, $A B$, separate printr-un spaţiu, reprezentând tipul îndoiturii ($A$ este $1$ dacă se realizează o îndoitură verticală sau $A$ este $2$ dacă se realizează o îndoitură orizontală), respectiv la ce distanţă se realizează îndoitura

Date de ieșire

Fişierul de ieşire origami.out va conţine, pe o singură linie, trei numere naturale nenule $H, L, G$, separate prin câte un spaţiu, reprezentând înălţimea, lăţimea şi respectiv grosimea obiectului obţinut.

Restricții și precizări

• $2 \leq N \leq 170$
• $1 \leq K \leq 2N - 2$
• $A = 1$ sau $A = 2$
• $1 \leq B <$ înălţimea sau lăţimea hârtiei la momentul respectiv (funcţie de tipul îndoiturii)

Exemplu

origami.in

4
3
1 3
2 3
1 1

origami.out

3 2 6

Explicație

Hârtia are $4$ unităţi înălţime şi $4$ unităţi lăţime.Prima îndoitură se realizează de la stânga la dreapta, de-a lungul celei de-a treia linii verticale faţă de marginea stângă a foii. Se obţine o foaie de înălţime $4$, lăţime $3$ şi grosime $2$. A doua îndoitură se realizează îndoind partea superioară a foii, în jos, de-a lungul celei de-a treia linii orizontale faţă se marginea de sus a foii. Se obţine un obiect de înălţime $3$, lăţime $3$ şi grosime $4$. După a treia îndoitură se obţine obiectul final, având înălţimea $3$, lăţimea $2$ şi grosimea $6$.