mesaj

În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii $M_i$ și $G_i$ se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul $M_i$ scrie și trimite un mesaj piticului $G_i$ respectând următoarele reguli:

• un mesaj conține una sau mai multe secvențe;
• orice literă care apare în mesaj, de cel puțin două ori, pe poziții alăturate, este numită terminator;
• o secvență se încheie când s-a întâlnit o succesiune de litere terminator;
• cuvântul este format din prima majusculă și ultima minusculă din secvență, fără a lua în seamă litera terminator a secvenței;
• o secvență ascunde un cuvânt dacă terminatorul său se repetă de exact două ori și dacă conține cel puțin o literă mare și o literă mică, ignorând terminatorul de secvență;
• costul unui cuvânt este egal cu numărul total de apariții al celor două litere din care este format, în cadrul secvenței în care a fost ascuns, luând în considerare inclusiv literele terminator.

De exemplu secvența $s f u E e t R u E E$ ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență, $E$, se repetă de exact două ori. Secvența ascunde cuvântul $Eu$, iar costul cuvântului este $5$ ($3$ litere $E$ + $2$ două litere $u$).

La primirea mesajului, piticul $G_i$ determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.

Cerinţe

Scrieţi un program care determină:

1. numărul de secvențe trimise care nu ascund cuvinte;
2. cuvintele din mesaj, în ordinea în care au fost trimise de piticul $M_i$;
3. pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de $G_i$.

Date de intrare

Fișierul de intrare mesaj.in conţine pe prima linie un număr natural $P$. Pentru toate testele de intrare, numărul $P$ poate avea numai una dintre valorile $1$, $2$ sau $3$. Pe a doua linie a fișierului de intrare se găsește numărul natural $N$ reprezentând numărul de litere folosite de $M_i$ pentru scrierea mesajului. Pe a treia linie se găsesc $N$ litere mari și mici ale alfabetului englez, separate prin câte un spațiu, reprezentând literele mesajului, în ordinea în care au fost trimise.

Date de ieşire

Dacă valoarea lui $P$ este $1$, se va rezolva numai punctul $1)$ din cerințe. În acest caz, fişierul de ieşire mesaj.out va conține pe prima linie un număr natural reprezentând răspunsul la cerinţa $1)$.

Dacă valoarea lui $P$ este $2$, se va rezolva numai punctul $2)$ din cerințe. În acest caz, fişierul de ieşire mesaj.out va conține cuvintele din mesaj, fiecare cuvânt scris pe câte o linie, în ordinea în care au fost trimise.

Dacă valoarea lui $P$ este $3$, se va rezolva numai punctul $3)$ din cerințe. În acest caz, fişierul de ieşire mesaj.out va conține pe fiecare linie câte o majusculă urmată de un număr natural nenul, separate printr-un spațiu. Majusculele vor fi afișate în ordine de la $A$ la $Z$, însă doar cele pentru care au existat în mesaj cuvinte care au început cu ele.

Restricţii și precizări

• $ 1 \leq N \leq 2000000$
• litera terminator a unei secvențe poate fi ori minusculă ori majusculă;
• ultimele litere din fișier sunt literele terminator ale ultimei secvențe din mesajul trimis;
• se garantează că în șirul de litere din fișierul de intrare se află ascuns cel puțin un cuvânt;
• majusculele alfabetului englez sunt $A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z$;
• pentru 50% din teste $N \leq 1000000$
• Pentru rezolvarea cerinţei $1)$ se acordă 20 de puncte, pentru rezolvarea cerinţei $2)$ se acordă 40 de puncte, iar pentru rezolvarea cerinţei $3)$ se acordă 40 de puncte.

Exemplul 1

mesaj.in

1
34
w w w w e D o r F D o r r t R n e R e y y j j i M o e i t t t j w w

mesaj.out

4

Explicație

Textul conține șase secvențe:
1) $w w w w$
2) $e D o r F D o r r$
3) $t R n e R e y y$
4) $j j$
5) $i M o e i t t t$
6) $j w w$

Sunt $4$ secvențe care nu ascund cuvinte:

• prima secvență și a patra deoarece conțin numai terminatorul;
• secvența a cincea nu se decodifică deoarece terminatorul se repetă de mai mult de două ori;
• secvența a șasea nu conține majuscule.

Exemplul 2

mesaj.in

2
34
u N a a e D o r F D o r r t R n e R e y y j j i M o e i t t t j w w

mesaj.out

Nu
Do
Re

Explicație

Textul conține șase secvențe:
1) $u N a a$
2) $e D o r F D o r r$
3) $t R n e R e y y$
4) $j j$
5) $i M o e i t t t$
6) $j w w$

Prima secvență are terminatorul $a$ care se repetă de două ori și ascunde cuvântul $Nu$.
A doua secvență are terminatorul $r$ și ascunde cuvântul $Do$.
A treia are terminatorul $y$ și ascunde cuvântul $Re$.
Ultimele trei secvențe nu ascund cuvinte.

Exemplul 3

mesaj.in

3
24
A a t t B b B t t e A e a n n B w I I F i e F F

mesaj.out

A 2
B 1
F 1

Explicație

Textul conține cinci secvențe:
1) $A a t t$
2) $B b B t t$
3) $e A e a n n$
4) $B w I I$
5) $F i e F F$

Cuvintele transmise în mesaj sunt:

• $Aa$ (cost $2$)
• $Bb$ (cost $3$)
• $Aa$ (cost $2$)
• $Bw$ (cost $2$)
• $Fe$ (cost $4$)

Costul maxim al cuvintelor care încep cu $A$ este $2$ și au fost $2$ cuvinte transmise. Pentru litera $B$ s-a transmis un singur cuvânt de cost maxim $3$.
Pentru litera $F$ s-a transmis un singur cuvânt de cost maxim $4$.