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?

Input

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.

Output

Word which has formed Vitek.