Задача . F. Строка и операции

Задана строка \(s\), состоящая из \(n\) символов. Эти символы являются первыми \(k\) строчными буквами латинского алфавита. Вам необходимо выполнить \(n\) операций со строкой.

Во время \(i\)-й операции вы берете символ, который первоначально занимал \(i\)-ю позицию, и выполняете с ним одно из следующих действий:

• поменять его местами с предыдущим символом в строке (если он существует). Эта операция записывается как L;
• поменять его местами со следующим символом в строке (если он существует). Эта операция записывается как R;
• циклически заменить его на предыдущий символ в алфавите (b становится a, c становится b и т. д.; a становится \(k\)-й буквой латинского алфавита). Эта операция записывается как D;
• циклически заменить его на следующий символ в алфавите (a становится b, b становится c и т. д.; \(k\)-я буква латинского алфавита становится a). Эта операция записывается как U;
• ничего не делать. Эта операция записывается как 0.

Пусть начальная строка — test, \(k = 20\), а последовательность операций — URLD. Тогда строка изменяется следующим образом:

1. первая операция U, поэтому мы меняем подчеркнутую букву в test на следующую из первых \(20\) латинских букв, т. е. на a. Теперь строка равна aest;
2. вторая операция R, поэтому мы меняем местами подчеркнутую букву со следующей в строке aest. Теперь строка равна aset;
3. третья операция L, поэтому мы меняем местами подчеркнутую букву с предыдущей в строке aset (обратите внимание, что теперь это \(2\)-й символ строки, но изначально он был \(3\)-м, поэтому к нему применяется \(3\)-я операция). Теперь строка равна saet;
4. четвертая операция D, поэтому мы меняем подчеркнутую букву в saet на предыдущую из первых \(20\) латинских букв, т. е. на s. Теперь строка равна saes.

Результатом выполнения последовательности операций является saes.

Для заданной строки \(s\) и значения \(k\) найдите лексикографически минимальную строку, которая может быть получена после применения последовательности операций к \(s\).