Problem C
Titans are in Danger!

Input: standard input
Output: standard output
Time Limit: 30 seconds

Fig: A simple case, when the number of Titans is two. The extra stone is between the two titans.

The Titans are in danger. They are trapped in a volcanic lake over a few stones. The number of stones is just one greater than the number of Titans. Only one Titan can stand over a stone at a time. They are mighty but helpless. They can see the shore but cannot reach it. The extra stone is of somewhat different nature. Once it is used, it sinks. But if the Titans can arrange themselves in a completely new orientation after that use, the stone rises again. The Titans could not figure out what to do? One of the merciful Gods became visible from the eastern sky and said,

“Use the stone to raise the stone….

When it finishes, you are free….”

So you are going to help them.

Note: The Titans can jump from one stone to another safely and easily if the target stone is vacant. No two Titans will have the same initial character in the name. Whenever the stone rises, the leftmost Titan loves to start. When all possible orientation is generated without repeating any state the Titans get free. A new state can be generated by exactly three jumps.

Input

The input file contains several lines of input. Each line describes an initial orientation of Titans (as a sequence of the initial character of their names). The maximum number of Titans is 9. Input is terminated by end of file.

Output

For each line of orientation you have to determine all possible orientations so that the titans become free. Print blank line after the output for each line of input.

Sample Input
ab

ugc

gucroth

Sample Output
ab

ba

ugc

guc

cug

ucg

gcu

cgu

gucroth

ugcroth

cguroth

gcuroth

ucgroth

cugroth

rugcoth

urgcoth

grucoth

rgucoth

ugrcoth

gurcoth

gcruoth

cgruoth

rgcuoth

grcuoth

crguoth

rcguoth

rcugoth

crugoth

urcgoth

rucgoth

curgoth

.

.

.

.

.

/***************Many lines of outputs here which are not shown****************/

.

.

.

.

.

rhcuotg

ruchotg

urchotg

cruhotg

rcuhotg

ucrhotg

curhotg

cuhrotg

uchrotg

hcurotg

churotg

uhcrotg

hucrotg

---

(Regional Warm-up Contest, Problem setter: Tanbir Ahmed)
( I would like to thank Hossain Muhammad Farook (University of Dhaka) for drawing the picture of the Titans)

A machine can do the work of fifty ordinary man, but no machine can do

the work of an extra-ordinary man.