Розворот префіксів#1718

Розворот префіксів

1 секунда

64 мегабайти

Легка

У Лабораторії Інтелектуальних Префіксних Алгоритмів (ЛІПА) тестують Машину, Префіксів Розгортаючу (МПР). Машина працює наступним чином: на вхід їй подається рядок $s$ довжини $n$ та послідовність $1 \leq a_{1} < a_{2} < \dots < a_{k} \leq n$ 1 \leq a_1 < a_2 < \ldots < a_k \leq n. Спочатку рядок $s$ поміщають у спеціальний внутрішній регістр машини. Після цього для кожного $i$ від $1$ до $k$ машина бере префікс $[1.. a_{i}]$ [1..a_i] поточного рядка та розгортає його. Рядок, який опиниться у регістрі після завершення роботи машини, є результатом роботи машини.

Наприклад, якщо на вхід машині подати рядок $abacaba$ та послідовність $a_{1} = 2$ a_1 = 2, $a_{2} = 4$ a_2 = 4, на виході отримаємо рядок $caababa$ .

Учені ЛІПА хочуть знайти для заданого рядка таку послідовність, щоб результат роботи був якомога меншим у лексикографічному порядку. Рядок $α = α_{1} α_{2} \dots α_{n}$ \alpha=\alpha_1\alpha_2 \ldots \alpha_n лексикографічно менший за рядок $β = β_{1} β_{2} \dots β_{m}$ \beta=\beta_1\beta_2 \ldots \beta_m, якщо для деякого $k$ і для всіх $1 \leq t \leq k$ 1 \leq t \leq k виконується $α_{t} = β_{t}$ \alpha_t=\beta_t та або $α_{k + 1} < β_{k + 1}$ \alpha_{k+1} < \beta_{k+1}, або довжина $α$ дорівнює $k$ , а довжина $β$ більша за $k$ .

Допоможіть їм з'ясувати, який мінімальний у лексикографічному порядку результат можна отримати.

Вхідні дані

Вхідний файл містить рядок $s$ (він непорожній і його довжина не перевищує $500000$ ). Він складається з малих літер латинського алфавіту.

Вихідні дані

Виведіть мінімальний у лексикографічному порядку рядок, який може бути отриманий МПР на рядку $s$ як на вході.

Приклади

Приклад 1