Olimpia D’Info a găsit o placă gravată ce conţine mai multe cuvinte scrise cu semne grafice necunoscute, fiecare cuvânt fiind format din exact 5 semne grafice. Studiind cu atenţie cuvintele, a dedus că în scrierea acestora sunt utilizate 12 semne grafice distincte şi a asociat câte o literă mică din alfabetul englez fiecărui semn. După asociere, a stabilit pentru fiecare semn o complexitate, scriind literele în ordinea crescătoare a complexităţilor pe care le-a stabilit anterior. Olimpia consideră că această ”complexitate” este cel mai potrivit criteriu de ordonare lexicografică.
Cerinţă
Cunoscând ordinea semnelor şi cuvintele de pe placă determinaţi:
a) Numărul de cuvinte distincte existente pe placă.
b) Şirul de cuvinte ordonat lexicografic, conform criteriului formulat de Olimpia.
Date de intrare
Fişierul de intrare zimeria.in conţine pe prima linie un numărul natural p din {1,2}, reprezentând varianta cerinţei de rezolvare. Pe a doua linie se află un număr natural n reprezentând numărul de cuvintede pe placă. Pe a treia linie sunt scrise 12 caractere, litere mici ale alfabetului englez, care reprezintă semnele codificate, în ordinea lexicografică a semnelor. Pe fiecare dintre următoarele n linii se află câte un cuvânt.
Date de ieşire
Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire zimeria.out va conţine pe prima linie numărul de cuvinte distincte de pe placă.
Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire zimeria.out va conţine n linii, pe fiecare linie câte un cuvânt în ordine lexicografică, conform complexităţii stabilite de către Olimpia.
Restricţii
• n < 400000
• 30% din teste vor avea pe prima linie valoarea 1, iar restul de 70% din teste vor avea pe prima linie valoarea 2.
Exemple
zimeria.in
zimeria.out
Explicaţii
1
5
qwertyuiopas
reeet
wyuty
reeet
oiopp
oiopp
3
Placa conţine 3 cuvinte distincte.
2
5
qwertyuiopas
oiopp
reeet
wyuty
reeet
oiopp
wyuty
reeet
reeet
oiopp
oiopp
Ordonăm cuvintele şi obţinem
wyuty
reeet
reeet
oiopp
oiopp