criptografie

Zedd a descoperit frumusețea aplicațiilor din domeniul criptografiei. Astfel, el și-a activat abilitățile de hacker și s-a lovit de următoarea problemă: fiind dat un șir format doar din litere mici ale alfabetului englez, Zedd trebuie să găsească secvențe pe care le poate forma fără ca vreo literă să apară de prea multe ori.

Cerință

Cunoscând textul lui Zedd, să se determine:

1. Numărul de secvențe distincte în care fiecare literă poate să apară de maximum $k$ ori. Două secvențe sunt considerate distincte dacă diferă fie prin poziția de început, fie prin cea de final.
2. Cea mai lungă secvență care conține doar litere distincte. Dacă sunt mai multe secvențe de lungime maximă formate din litere distincte se alege prima din punct de vedere lexicografic (alfabetic).

Date de intrare

Fișierul de intrare criptografie.in conţine pe prima linie cerința $C$ (care poate fi $1$ sau $2$), pe linia a doua numărul natural $k$, cu semnificația de mai sus, precum și un număr natural $n$, separate printr-un spațiu. Pe a treia linie se află un text format din $n$ litere mici ale alfabetului englez (neseparate prin spații).

Date de ieșire

Fișierul de ieşire criptografie.out va conţine pe prima linie:

• Dacă $C=1$, un număr natural ce reprezintă răspunsul la cerința 1.
• Dacă $C=2$, șirul ce reprezintă răspunsul la cerința 2.

Restricții și precizări

• O secvență este formată dintr-o succesiune de litere aflate pe poziții consecutive într-un șir;
• $0 \lt n \leq 10^5$;
• $0 \lt k \leq n$;
• Pentru teste în valoare de 67 de puncte $C = 1$, iar pentru 33 de puncte $C = 2$;
• Pentru teste în valoare de 17 puncte se garantează $C = 1$, $k = 1$ și $n \leq 100$;
• Pentru teste în valoare de alte 17 puncte se garantează $C = 1$ și $n \leq 1 \ 000$;
• Pentru cerința 2 se garantează că valoarea lui $k$ este $1$.

Exemplul 1

criptografie.in

1
1 4
abac

criptografie.out

8

Explicație

Pentru textul dat, variantele care ar putea fi obținute conform cerinței sunt: a, ab, b, ba, bac, a, ac, c.
În total numărul de secvențe cu caractere distincte ($k = 1$) ce pot fi formate este $8$.

Exemplul 2

criptografie.in

2
1 6
abacba

criptografie.out

acb

Explicație

Lungimea maximă a unei secvențe de elemente distincte este $3$. Sunt trei astfel de secvențe. Prima din punct de vedere alfabetic este acb.