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

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$

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

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

0 0   0 1
0 0   0 0

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

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

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

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

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

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