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