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