У Лабораторії Інтелектуальних Префіксних Алгоритмів (ЛІПА) тестують Машину Префікси Розвертаючу (МПР). Машина працює наступним чином: на вхід їй подається рчдок \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} у якості вхідного.