eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 0.1 секунд
Ліміт використання пам'яті 64 MiB

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

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

Вхідні дані

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

Вихідні дані

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

Приклад

Вхідні дані #1
CBABC
Вихідні дані #1
ABCCB