Задана строка $$$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$$$.