The Titans are in danger. They are trapped in a vol- canic 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 can- not 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 orienta- tion 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 an- other 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 A simple case, when the number of Titans is two. The extra stone is between the two titans.
2/3 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
3/3 uhcrotg hucrotg