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

Разворот префиксов

Разворот префиксов

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

В Лаборатории Интеллектуальных Префиксных Алгоритмов (ЛИПА) тестируют Машину, Префиксов Разворачивающую (МПР). Машина работает следующим образом: на вход ей подается строка s длины n и последовательность 1a_1 < a_2 < ... < a_kn. Исходно строка s помещается в специальный внутренний регистр машины. После этого для каждого i от 1 до k машина берет префикс [1..a_i] текущей строки и разворачивает его. Строка, которая оказывается в регистре после окончания работы машины представляет собой результат работы машины.

Например, если на вход машине подать строку "abacaba" и последовательность a_1=2, a_2=4, на выходе получится строка "caababa".

Ученые ЛИПА хотят найти для заданной строки такую последовательность, чтобы результат работы оказался как можно меньше в лексикографическом порядке. Строка α=α_1α_2...α_n лексикографически меньше строки β=β_1β_2...β_m, если для некоторого k и для всех 1tk верно α_t = β_t и либо α_{k+1} < β_{k+1}, либо длина α равна k, а длина β больше k.

Помогите им выяснить, какой минимальный лексикографически результат можно получить.

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

Входной файл содержит строку s (она непуста и ее длина не превышает 500000). Она состоит из строчных букв латинского алфавита.

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

Выведите минимальную в лексикографическом порядке строку, которая может быть выведена МПР на строке s в качестве входа.

Пример

Входные данные #1
abacaba
Выходные данные #1
aaaabcb