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

Детская железная дорога

Детская железная дорога

Лимит времени 0.1 секунд
Лимит использования памяти 64 MiB

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

Какое слово получится у Витэка?

Входные данные

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает 500000.

Выходные данные

Слово, которое образовал Витэк.

Пример

Входные данные #1
CBABC
Выходные данные #1
ABCCB