Разворот префиксов
В Лаборатории Интеллектуальных Префиксных Алгоритмов (ЛИПА) тестируют Машину, Префиксов Разворачивающую (МПР). Машина работает следующим образом: на вход ей подается строка s длины n и последовательность 1 ≤ a_1 < a_2 < ... < a_k ≤ n. Исходно строка s помещается в специальный внутренний регистр машины. После этого для каждого i от 1 до k машина берет префикс [1..a_i] текущей строки и разворачивает его. Строка, которая оказывается в регистре после окончания работы машины представляет собой результат работы машины.
Например, если на вход машине подать строку "abacaba" и последовательность a_1=2, a_2=4, на выходе получится строка "caababa".
Ученые ЛИПА хотят найти для заданной строки такую последовательность, чтобы результат работы оказался как можно меньше в лексикографическом порядке. Строка α=α_1α_2...α_n лексикографически меньше строки β=β_1β_2...β_m, если для некоторого k и для всех 1 ≤ t ≤ k верно α_t = β_t и либо α_{k+1} < β_{k+1}, либо длина α равна k, а длина β больше k.
Помогите им выяснить, какой минимальный лексикографически результат можно получить.
Входные данные
Входной файл содержит строку s (она непуста и ее длина не превышает 500000). Она состоит из строчных букв латинского алфавита.
Выходные данные
Выведите минимальную в лексикографическом порядке строку, которая может быть выведена МПР на строке s в качестве входа.