URI Online Judge | 1556

Removing Letters

By Gabriel Dalalio, ITA BR Brazil

Timelimit: 4

João challenged Pedro in a game involving sequences of letters.

In the beginning, it is shown to the players a sequence of letters. Each player must try to use this sequence to form other sequences. Therefore, it is allowed to remove letters of the sequence, without changing the order. The player who can form more distinct sequences wins the game.

Pedro would like your help to beat João in this game. Your task is to show Peter all distinct sequences, in alphabetical order, he may form during the game.

Input

The input contains several test cases. Each test case consists of a line containing a sequence to be used in the game. The sequence is formed only by lowercase characters and can contain up to 1000 characters.

Output

For each test, the output consists of several lines containing all sequences that may be formed by Pedro during the game. It is guaranteed to all entries that are no more than 1000 possible sequences to be formed. Print a blank line after each test case.

Sample Input Sample Output

abc
aaaaa
huehue

a
ab
abc
ac
b
bc
c

a
aa
aaa
aaaa
aaaaa

e
ee
eh
ehe
ehu
ehue
eu
eue
h
he
hee
heh
hehe
hehu
hehue
heu
heue
hh
hhe
hhu
hhue
hu
hue
huee
hueh
huehe
huehu
huehue
hueu
hueue
huh
huhe
huhu
huhue
huu
huue
u
ue
uee
ueh
uehe
uehu
uehue
ueu
ueue
uh
uhe
uhu
uhue
uu
uue