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