anagrame

Se dă un cuvânt format numai din litere mici. Numim anagramă un cuvânt format din literele cuvântului dat, schimbând eventual ordinea literelor. De exemplu o anagramă a cuvântului tamara este cuvântul armata. Evident, un cuvânt poate fi considerat o anagramă a lui însuşi.

Cerință

Scrieţi un program care să genereze toate anagramele unui cuvânt dat, în ordine lexicografică.

Date de intrare

Fişierul de intrare anagrame.in conţine pe prima linie cuvântul dat.

Date de ieșire

Fişierul de ieşire anagrame.out va conţine în ordine anagramele cuvântului dat, câte una pe linie.

Restricții și precizări

• Cuvântul dat are cel mult $10$ litere mici.
• Cuvântul $x = x_1 \ x_2 \dots x_n$ precede cuvântul $y = y_1 \ y_2 \dots y_n$ dacă există un indice $k \in {1, 2, \dots, n}$ astfel încât $x_i = y_i$, $i \in {1, 2, \dots, k - 1}$, iar litera $x_k$ precede în alfabet litera $y_k$.

Exemplu

anagrame.in

ana

anagrame.out

aan
ana
naa