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

RAU-Gigel este pasionat de grafică, aşa că se gândeşte la un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni N X N pixeli. O imagine bitmap binară este o matrice de pixeli, fiecare pixel fiind un bit. Să considerăm că valoarea 0 (nesetat) înseamnă alb şi valoarea 1 (setat) înseamnă negru (în realitate este exact invers!). Apoi RAU-Gigel împarte imaginea în patru imagini pătrate egale de latură N / 2 pe care le notează de la 1 la 4 (1 este imaginea din colţul dreapta-sus, 2 este cea din colţul dreapta-jos, 3  stânga-jos şi 4  stânga-sus). El repetă procedeul pentru fiecare dintre cele 4 imagini obţinute, şi tot aşa, reducând mereu latura la jumătate şi notând direcţiile de la 1 la 4, până când ajunge la imagini de mărimea unui pixel.

RAU-Gigel este pasionat de grafică, aşa că se gândeşte la un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni $N X N$ pixeli. O imagine bitmap binară este o matrice de pixeli, fiecare pixel fiind un bit. Să considerăm că valoarea 0 (nesetat) înseamnă alb şi valoarea 1 (setat) înseamnă negru (în realitate este exact invers!). Apoi RAU-Gigel împarte imaginea în patru imagini pătrate egale de latură $N / 2$ pe care le notează de la $1$ la $4$ ( $1$ este imaginea din colţul dreapta-sus, $2$ este cea din colţul dreapta-jos, $3$  stânga-jos şi $4$  stânga-sus). El repetă procedeul pentru fiecare dintre cele $4$ imagini obţinute, şi tot aşa, reducând mereu latura la jumătate şi notând direcţiile de la $1$ la $4$, până când ajunge la imagini de mărimea unui pixel.

Pentru simplitate, să presupunem că N este o putere a lui 2, să spunem K. Deci, după K împărţiri succesive de imagini, orice pixel poate fi identificat printr-un şir unic format din cifrele 1, 2, 3 şi 4, de lungime K.

Pentru simplitate, să presupunem că $N$ este o putere a lui $2$, să spunem $K$. Deci, după $K$ împărţiri succesive de imagini, orice pixel poate fi identificat printr-un şir unic format din cifrele $1$, $2$, $3$ şi $4$, de lungime $K$.

De exemplu, dacă N = 4, atunci K = 2. Imaginea iniţială are 16 pixeli. Vom avea 2 împărţiri succesive:

De exemplu, dacă $N = 4$, atunci $K = 2$. Imaginea iniţială are $16$ pixeli. Vom avea $2$ împărţiri succesive:

După prima împărţire rezultă 4 imagini reduse la jumătate (fiecare are câte 4 pixeli):
4 1
3 2

După prima împărţire rezultă $4$ imagini reduse la jumătate (fiecare are câte $4$ pixeli):
$4  1$
$3  2$

După a doua împărţire rezultă @16@ imagini de câte @1@ pixel:
@44@ @41@ \(\quad\) @14@ @11@
@43@ @42@ \(\quad\) @13@ @12@

După a doua împărţire rezultă $16$ imagini de câte $1$ pixel:
$44 41    14 11$
$43 42    13 12$

@34@ @31@ \(\quad\) @24@ @21@
@33@ @32@ \(\quad\) @23@ @22@

$34 31    24 21$
$33 32    23 22$

Iniţial, imaginea este complet albă.

Acum începe jocul. RAU-Gigel se gândeşte la @2@ tipuri de operaţii:
Operaţia @1 x@ schimbă starea pixelul identificat cu şirul @x@, descris ca mai sus. Dacă pixelul @x@ nu este setat, îl setează. Dacă pixelul @x@ este deja setat, atunci îl resetează.
Operaţia @2 x@ , unde @x@ are aceeaşi semnificaţie ca mai sus, este o interogare: dacă @x@ este setat, se răspunde cu @0@. Dacă @x@ nu este setat, se cere determinarea dimensiunii celei mai mari imagini complet albe, dintre cele create de RAU-Gigel, care conţine pixelul @x@. Dimensiunea este dată de numărul de pixeli conţinut.

Acum începe jocul. RAU-Gigel se gândeşte la $2$ tipuri de operaţii:
Operaţia $1 x$ schimbă starea pixelul identificat cu şirul $x$, descris ca mai sus. Dacă pixelul $x$ nu este setat, îl setează. Dacă pixelul $x$ este deja setat, atunci îl resetează.
Operaţia $2 x$ , unde $x$ are aceeaşi semnificaţie ca mai sus, este o interogare: dacă $x$ este setat, se răspunde cu $0$. Dacă $x$ nu este setat, se cere determinarea dimensiunii celei mai mari imagini complet albe, dintre cele create de RAU-Gigel, care conţine pixelul $x$. Dimensiunea este dată de numărul de pixeli conţinut.

Dându-se @N@ cu semnificaţia de mai sus şi @M@, reprezentând numărul de operaţii şi cele @M@ operaţii de tipul @1@ şi @2@, să se răspundă la operaţiile de tip @2@.
 
h1. Date de intrare

Dându-se $N$ cu semnificaţia de mai sus şi $M$, reprezentând numărul de operaţii şi cele $M$ operaţii de tipul $1$ şi $2$, să se răspundă la operaţiile de tip $2$.

h2. Date de intrare

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

Fişierul de intrare $pixeli.in$ conţine pe prima linie numerele naturale $N$ şi $M$ separate cu un spaţiu. Pe următoarele $M$ linii se află câte o cifră de $1$ sau $2$ şi câte un string, de forma $tip_operaţie x$, reprezentând tipul operaţiei şi şirul $x$.

h2. Date de ieşire

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

Fişierul de ieşire $pixeli.out$ va conţine răspunsurile pentru operaţiile de tip $2$, câte unul pe linie.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 2.000.000.000$, $1 ≤ M ≤ 10.000$
* In toate testele, $N$ este o putere a lui $2$
* Toate şirurile $x$ sunt corect definite
* Pentru teste în valoare de $30$ de puncte $N <= 1.000$ şi $M <= 50$

h2. Exemplu
table(example). |_. pixeli.in |_. pixeli.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 11
1 11
1 22
2 22
2 33
2 44
2 24
1 22
2 22
2 24
1 11
2 44
| 0
4
4
1
4
4
16

|
h3. Explicaţie

...

Iniţial imaginea este albă:
$0 0    0 0$
$0 0    0 0$
 
$0 0    0 0$
$0 0    0 0$
 
După primele $2$ operaţii de tip $1$, imaginea va conţine:
$0 0    0 1$
$0 0    0 0$
 
$0 0    0 0$
$0 0    0 1$
 
Următoarele $4$ interogări vor referi, în ordine, pixelii marcati cu $a$, $b$, $c$, $d$ (imaginea de mai jos). Cum $a$ era setat, răspunsul este $0$. Cea mai mare imagine albă, creată de RAU-Gigel, care conţine $b$, este colţul stânga jos cu $4$ pixeli. La fel pentru $c$. În cazul pixelului $d$, răspunsul este $1$ (chiar el).
$c 0    0 e$
$0 0    0 0$
 
$0 0    d 0$
$b 0    0 a$
 
Urmează o operaţie de tip $1$ care resetează pixelul notat cu $a$ (şirul $22$). Următoarele $2$ interogări pentru $a$ şi $d$ generează răspunsurile $4$, respectiv $4$.
 
În final, se resetează şi pixelul $e$, iar ultima interogare, pentru $c$, va determina răspunsul $16$, toată imaginea fiind acum complet albă.

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