Valoarea unei litere este dată de numărul ei de ordine în alfabet (A are valoarea 1, B are valoarea 2, C are valoarea 3, etc.). Un text special este format din una sau mai multe litere mari ale alfabetului englez și nu conține alte tipuri de caractere. Valoarea unui text special o definim ca fiind egală cu suma valorilor literelor care îl compun. De exemplu, textul special ABAC are valoarea 7 (7=1+2+1+3).

Un text special poate fi transcris într-o formă restrânsă prin utilizarea perechilor de paranteze și a numerelor naturale. De exemplu, transcrierea în forma restrănsă a textului ABACABACEECDCDE este textul (ABAC)2E2(CD)2E deoarece secvența ABAC apare de două ori consecutiv, litera E are două apariții consecutive și la fel secvența de litere CD.

Transcrierea în formă restrânsă a unui text special se realizează prin înlocuirea fiecărei secvențe care are apariții consecutive în text cu secvența scrisă între o pereche de paranteze rotunde urmată apoi de numărul de repetiții. De exemplu, textul special ABABAB se transcrie în forma restrânsă în (AB)3.

Dacă, după transcriere, textul în formă restrânsă conține secvențe care au apariții consecutive în text atunci și acesta se va transcrie în formă restrânsă. De exemplu, textul special ABABCABABC se poate transcrie întâi în forma restrânsă în (ABABC)2 sau în (AB)2C(AB)2C iar apoi în ((AB)2C)2.

Dacă textul special nu conține nicio secvență cu apariții consecutive în text, atunci forma restrânsă a textului este identică cu forma inițială. De exemplu, textul special ABAC are forma restrânsă ABAC care este identică cu acest text special.

Cerința

Scrieți un program care citește un șir de caractere S reprezentând forma restrânsă a unui text special, și apoi determină:

1. numărul literelor distincte care apar în textul special;
2. suma numerelor care apar în forma restrânsă a textului special;
3. valoarea textului special dat în forma restrânsă.

Date de intrare

Fișierul de intrare valoare.in conține:

• pe prima linie, un număr natural C (1, 2 sau 3) reprezentând cerința care trebuie rezolvată;
• pe a doua linie, șirul de caractere S reprezentând forma restrânsă a unui text special.

Date de ieșire

Fișierul de ieșire valoare.out va conține pe prima linie:

• dacă C = 1, un număr natural reprezentând numărul literelor distincte care apar în textul special (răspunsul la cerința 1);
• dacă C = 2, pe prima linie, un număr natural reprezentând suma numerelor care apar în forma restrânsă a textului special (răspunsul la cerința 2);
• dacă C = 3, pe prima linie, un număr natural reprezentând valoarea textului special dat în forma restrânsă (răspunsul la cerința 3).

Restricții și precizări

• Șirul de caractere S ce reprezintă forma restrânsă a unui text special poate avea cel mult 1000 de caractere (litere mari ale alfabetului englez, perechi de paranteze rotunde, cifre).
• Numerele naturale care apar în forma restrânsă a unui text special sunt nenule și aparțin intervalului închis [2, 9999].
• Valoarea unui text special este un număr natural format din cel mult 12 cifre.
• Pentru cerința 1 se acordă 10p, pentru cerința 2 se acordă 20p, iar pentru cerința 3 se acordă 70p.
• Pentru teste în valoare de 10p, formă restrânsă a textului special este identică cu textul special și cerința este 3.

Exemplul 1:

valoare.in

1
(ABAC)2E2(CD)2E

valoare.out

5 

Explicație

Se rezolvă cerința 1.

Forma restrânsă a textului special este (ABAC)2E2(CD)2E. În textul special apar doar literele A, B, C, D și E.

Exemplul 2:

valoare.in

2
(ABAC)2E2(CD)2E

valoare.out

6 

Explicație

Se rezolvă cerința 2.

Se rezolvă cerința 2. Forma restrânsă a textului special este (ABAC)2E2(CD)2E. În textul special apare doar numărul 2, de 3 ori. Astfel suma este 6 (=2+2+2).

Exemplul 3:

valoare.in

3
(ABAC)2E2(CD)2E

valoare.out

43 

Explicație

Se rezolvă cerința 3.

Forma restrânsă (ABAC)2E2(CD)2E reprezintă transcrierea textului special ABACABACEECDCDE. În textul special apar 4 de A, 2 de B, 4 de C, 2 de D și 3 de E. Astfel, valoarea textului special este egală cu 43 (=4*1+2*2+4*3+2*4+3*5).