Pixeli

RAU-Gigel este pasionat de grafică, așa că se gândește să vă facă un cadou de 1 Iunie: un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni $N \times 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. 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$.

De exemplu, dacă $N = 4$, atunci $K = 2$. Vom avea $2$ împărțiri succesive:

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.

Cerință

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.

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

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.

Restricții și precizări

• $2 \le N \le 2\ 000\ 000\ 000$
• $1 \le M \le 10\ 000$
• În toate testele, $N$ este o putere a lui $2$.
• Toate șirurile $x$ sunt corect definite.
• Pentru teste în valoare de 30 de puncte, $N \le 1\ 000$ și $M \le 50$.

Exemplul 1

pixeli.in

4 11
1 11
1 22
2 22
2 33
2 44
2 24
1 22
2 22
2 24
1 11
2 44

pixeli.out

0
4
4
1
4
4
16

Explicație

Inițial imaginea este albă:

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 (bolduit). 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$.

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

Exemplul 2

pixeli.in

8 9
1 111
1 222
2 222
2 333
2 444
2 242
1 222
2 222
2 242

pixeli.out

0
16
16
4
16
16