Дитяча залізниця

Вітек не припиняє своїх забавок з кубиками. А тут ще татко подарував йому дитячу залізницю. Вітек розташовує якусь кількість кубиків по одному на вагончик і перед тим, як завершити гру, вирішує переформувати потяг таким чином, щоб отримане слово було лексикографічно найменшим із усіх можливих, але так як він до цього вже награвся, то може лише один раз від'єднати якусь кількість кубиків і паровозиком перевезти їх у хвіст свого потягу.

Яке слово отримає Вітек?

Вхідні дані

Перший і єдиний рядок містить задане слово. Кубики у Вітека лише з великих літер латинського алфавіту і їх кількість не перевищує 500000.

Вихідні дані

Слово, утворене Вітеком.

Приклади