ID #123 · Colecția InfoAs · Operatori și expresii

Problema 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 × 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 1` `3 2` După a doua împărțire rezultă `16` imagini de câte `1` pixel: `44 41 14 11` `43 42 13 12` ` ` `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: 1. 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ă. 2. 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 ≤ N ≤ 2.000.000.000` * `1 ≤ M ≤ 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 ≤ 1.000` și `M ≤ 50`