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ța

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 ≤ n, m ≤ 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.