În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii Mi și Gi se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul Mi scrie și trimite un mesaj piticului Gi 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 Gi 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 Mi;
3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de Gi.

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

1. Aa (cost 2)
2. Bb (cost 3)
3. Aa (cost 2)
4. Bw (cost 2)
5. 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.