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

$3  2$
După a doua împărţire rezultă $16$ imagini de câte $1$ pixel:

$44 41    14 11$
$43 42    13 12$

$44$ $41$  $14$ $11$
$43$ $42$  $13$ $12$

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

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

Iniţial, imaginea este complet albă.

h2. Date de intrare

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

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

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

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$

* 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

h3. Explicaţie
Iniţial imaginea este albă:

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

$0 0    0 0$
$0 0    0 1$

După primele 2 operaţii de tip 1, imaginea va conţine:

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   0 1
0 0   0 0

$0 0    d 0$
$b 0    0 a$

0 0   0 0
0 0   0 1

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

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

În final, se resetează şi pixelul $e$, iar ultima interogare, pentru $c$, va determina răspunsul $16$, toată imaginea fiind acum complet albă.

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") ==