Лимак — маленький полярный медведь. Ему нравятся красивые строки — строки длины n, состоящие из маленьких английских букв.

Расстоянием между двумя буквами будем называть разницу их позиций в алфавите. Например, , а .

Определим расстояние между двумя красивыми строками как сумму расстояний соответствующих букв. Например, , а .

У Лимака есть красивая строка s и целое число k. Вам требуется найти любую красивую строку s' такую, что или определить, что такой строки не существует.

Рекомендуется для ввода и вывода данных использовать функции gets, scanf, printf в языке C++, поскольку они работают значительно быстрее чем getline, cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.