The children`s railway

The children`s railway


Vitek does not stop the games with cubes. And that still the daddy has presented it the children's railway. Vitek places any quantity of cubes on one on car and before finishing game, decides to reconstruct structure so that the turned out word was leksicographics least of all possible but as it has already played enough, therefore can unhook only once any quantity of cubes and a steam locomotive to transport them in a tail of the structure.

What word will turn out at Viteks?


The first and unique line contains an initial word. At Viteks only from capital letters of the latin alphabet and their quantity does not exceed cubes 500000.


Word which has formed Vitek.

Time limit 0.1 seconds
Memory limit 64 MiB
Input example #1
Output example #1