raganama

La naşterea unei fete în tribul Ragan Ama părinţii trebuie să îi găsească cel mai frumos nume posibil. Sunt considerate nume frumoase doar anagramele unui cuvânt care, în limba lor, înseamnă “frumoasă ca roua dimineţilor, blândă ca mângâierea vântului printre frunze, binecuvântată de lumina soarelui şi a lunii”.
Viaţa fetei va sta sub o stea norocoasă dacă numele său este cel mai mic din punct de vedere lexicografic, diferit de al oricăreia dintre fetele din trib.

Cerinţă

Fiindcă astăzi în trib s-a născut o fetiţă, scrieţi un program care, cunoscând numele fetelor din trib, rezolvă următoarele cerinţe:

1. afişează numele pe care părinţii ar trebui să i-l dea fetei pentru ca viaţa să-i stea sub o stea norocoasă;
2. determină câte nume frumoase, diferite de cele ale fetelor din trib, există.

Date de intrare

Fişierul de intrare raganama.in conţine pe prima linie un număr natural $C$, care reprezintă cerinţa care trebuie să fie rezolvată ($1$ sau $2$). Pe următoarele linii se află numele fetelor din trib, câte un nume pe o linie, în ordine lexicografică; toate numele sunt anagrame ale aceluiași cuvânt.

Date de ieşire

Fişierul de intrare raganama.out va conţine o singură linie.

• Dacă $C = 1$, pe această linie pe care va fi scris numele pe care părinţii ar trebui să i-l dea fetei.
• Dacă $C = 2$, pe această linie va fi scris numărul de nume frumoase, diferite de cele ale fetelor din trib.

Restricţii şi precizări

• Numele fetelor sunt formate din maximum $100$ de litere mici din alfabetul englez.
• În trib există maximum $100 \ 000$ de fete.
• O anagramă a unui cuvânt este formată din aceleaşi litere cu cuvântul dat, eventual într-o altă ordine. De exemplu cuvântul “armata” este o anagramă a cuvântului “tamara”.
• Spunem că un cuvânt $a_1 \ a_2 \dots \ a_n$ este mai mic din punct de vedere lexicografic decât un cuvânt $b_1 \ b_2 \dots \ b_n$ dacă există $1 \leq k \leq n$ astfel încât $a_i = b_i$, pentru orice $1 \leq i < k$ şi $a_k < b_k$.
• Se garantează că pentru datele de test există un nume ce poate fi dat fetei nou-născute.
• Pentru teste valorând $20$ de puncte rezultatul la cerinţa $2$ va avea maximum $18$ cifre.
• Pentru teste valorând $50$ de puncte cerința este $1$.

Exemplul 1

raganama.in

1
aacn
aanc
acan
acna
anac
caan
cana

raganama.out

anca

Exemplul 2

raganama.in

2
aacn
aanc
acan
acna
anac
caan
cana

raganama.out

5

Explicație

Există în total $12$ anagrame:

aacn
aanc
acan
acna
anac
anca
caan
cana
cnaa
naac
naca
ncaa

Primul nume în ordine lexicografică care nu aparţine niciunei fete din trib este anca. Dintre cele $12$ anagrame existente, $7$ sunt deja numele unor fete din trib, deci mai exista $12 - 7 = 5$ nume frumoase.