405039: GYM101745 D Stamp Stamp Stamp
Description
Cat Noku has a strip of paper that consists of n blank cells lying side by side. He has a painting s he wants to paint. This means, he would like to paint it so that the the i-th cell will contain color si (here, colors are represented by letters 'a'-'z'). He is not allowed to shift, turn or flip the strip. We consider that at the beginning each cell has no color assigned to it.
Cat Noku only has enough money to buy a single stamp. The stamp will consist of k units (1 ≤ k ≤ n), and each section is colored some arbitrary color. We denote the colors of the stamp as t1, t2, ..., tk. However, the value of k and exact colors of the stamp are yet to be defined.
To use the stamp, it must first be aligned with exactly k of the neighboring units on the paper. The stamp cannot extend beyond the ends of the paper, nor can it cover fractions of units. Once placed, the stamp paints the k covered units so that the i-th section from the left is painted color i. It is not allowed to turn or flip the stamp. It is allowed that the cell of the strip is colored multiple times, possible with different colors. The final color of the strip cell is equal to the color of the last stamp cell that was placed on it.
Given the string s, output the stamps that Cat Noku could have chosen to paint the string. Output these stamps in lexicographic order.
InputThe first and only line of input contains a single string s (1 ≤ |s| ≤ 150).
OutputPrint the stamps that could have produced this string in lexicographic increasing order.
ExamplesInputaaaaaOutput
aInput
aa
aaa
aaaa
aaaaa
babaabaOutput
baNote
baaba
baba
babaaba
In the second sample, Cat Noku can stamp out babaaba from ba as follows:
- ...ba..
- ..baa..
- babaa..
- babaaba