virus

Există azi mulţi viruşi care acţionează în diferite moduri asupra informaţiei stocate într-un calculator. Printre aceştia există şi unii mai puţin periculoşi, care se mulţumesc doar să simuleze o anumită alterare a informaţiei. Să presupunem că dorim să scriem un astfel de virus care acţionează doar asupra informaţiei de tip text de pe ecranul calculatorului. În mod text, ecranul este constituit din $n$ linii pe fiecare aflându-se câte $m$ caractere. Caracterele sunt reţinute în memoria calculatorului prin codul lor ASCII, reprezentat în binar pe $8$ biţi. Biţii sunt numerotaţi de la $0$ la $7$ de la dreapta către stânga, cel din stânga fiind cel mai semnificativ bit.

La fiecare secundă, virusul transformă simultan toate caracterele de pe ecran după următoarele reguli:

1. virusul afectează doar caracterele ale căror coduri nu are toți biții egali cu $0$; caracterul al cărui cod are toţi biţii egali cu $0$ se numește inatacabil;
2. se determină caracterele ale căror coduri au număr maxim de biți egali cu $1$; pentru fiecare astfel de caracter cei mai semnificativi $2$ biţi egali cu $1$ din cod se transformă în $0$, iar dacă nu are în cod $2$ biţi egali cu $1$, se va transforma în $0$ singurul bit $1$ existent;
3. pentru toate celelalte caractere atacabile, bitul cel mai puţin semnificativ egal cu $0$ al codului se transformă în $1$;
4. unele caractere pot genera erori în execuţia virusului deoarece transformând succesiv codurile lor se pot obţine cicluri; aceste caractere au codurile ASCII $1$, $3$, $7$, $15$, $31$, $63$, $127$ şi virusul le transformă imediat în $0$ (adică devin inatacabile), indiferent când un astfel de caracter apare (adică dacă el există iniţial pe ecran sau apare după o transformare).

Cerinţă

Cunoscând configuraţia iniţială a ecranului, scrieţi un program care să rezolve următoarele două cerinţe:

1. determină numărul de caractere inatacabile obţinute în prima secundă (adică după prima transformare);
2. determină după câte secunde toate caracterele de pe ecran sunt inatacabile.

Date de intrare

Fișierul de intrare virus.in conţine pe prima linie două numere naturale separate printr-un spațiu $n$, $m$, reprezentând dimensiunile ecranului. Pe fiecare dintre următoarele $n$ linii se află câte $m$ caractere, reprezentând caracterele existente iniţial pe ecran. Ultima linie a fișierului de intrare conține cerinţa care trebuie să fie rezolvată ($1$ sau $2$).

Date de ieșire

Fișierul de ieșire virus.out va conține o singură linie pe care va fi scris un număr natural, reprezentând răspunsul la cerinţa specificată în fişierul de intrare.

Restricții și precizări

• $1 \leq n, m \leq 100$
• Caracterele aflate inițial pe ecran au coduri cuprinse între $32$ şi $127$.
• Pentru teste valorând $30$ de puncte, cerința este $1$.

Exemplul 1

virus.in

2 2
AA
AA
1

virus.out

4

Explicație

Caracterul $A$ are codul $01000001$, deci numărul maxim de biți egali cu $1$ este $2$ (egal pentru toate caracterele); după o secundă toate cele $4$ caractere vor avea codul $00000000$ (deci devin inatacabile).

Exemplul 2

virus.in

3 3
AAC
AAC
CCC
2

virus.out

2

Explicație

În prima secundă:

• numărul maxim de biți egali cu $1$ în codurile caracterelor este $3$ ($C$ având codul $01000011$); după eliminarea celor mai semnificativi doi biți $1$ codul lui $C$ devine $00000001$, deci devine un caracter care generează erori şi virusul îl transformă imediat în $00000000$ (inatacabil);
• celelalte caractere $A$ (cu codul $01000001$) devin $C$ (codul $01000011$).

În a doua secundă numărul maxim de biți egali cu $1$ este $3$, se elimină cei mai semnificativi doi biți $1$, codul devine $00000001$ rezultă un caracter care generează erori, deci virusul îl transformă în inatacabil. Astfel, după două secunde toate caracterele sunt inatacabile.