Cerința

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.

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 \(\quad\) 1
3 \(\quad\) 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

34 31 \(\quad\) 24 21
33 32 \(\quad\) 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.

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 ≤ 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

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ă:
0 0 \(\quad\) 0 0
0 0 \(\quad\) 0 0

0 0 \(\quad\) 0 0
0 0 \(\quad\) 0 0

După primele 2 operații de tip 1, imaginea va conține:
0 0 \(\quad\) 0 1
0 0 \(\quad\) 0 0

0 0 \(\quad\) 0 0
0 0 \(\quad\) 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 \(\quad\) 0 e
0 0 \(\quad\) 0 0

0 0 \(\quad\) d 0
b 0 \(\quad\) 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ă.

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