Реверсування Префіксів

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

Наприклад, якщо на вхід машині подано s= \texttt{abacaba} і a_1 = 2, a_2 = 4, то результатом роботи буде $\text{caababa}$.

Вчені LIPA хочуть знайти лексикографічно найменший рядок, який може вийти на виході машини для заданого $s$. Допоможіть їм у цьому завданні.