Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


6. Глухой телефон

Автор задачи: Хаустов Павел
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 1 с.
Ограничение по памяти: 128 МБ

На дне рождения Паши собрались n гостей. После того как они съели весь торт, стало очень скучно. Чтобы развлечь своих гостей Паша предложил сыграть в одну достаточно интересную игру. Суть игры заключается в следующем: Паша рассаживает всех гостей друг за другом в цепочку и загадывает некоторое слово длины l, состоящее из строчных букв латинского алфавита. Затем Паша сообщает загаданное слово первому в цепочке гостю. После чего первый гость передает услышанное им слово следующему гостю в этой цепочке. Так происходит до тех пор, пока последний гость в цепочке не услышит загаданное слово.

Так как в комнате очень шумно при передаче слова очередному гостю, одна буква в слове искажается. Все гости пронумерованы последовательными целыми числами от 1 до n в порядке передачи слова. Все буквы слова так же пронумерованы целыми последовательными числами от 1 до l. Гость с номером i искажает букву с номером (i - 1) mod l + 1.

Под искажением некоторой буквы слова понимается смещение этой буквы на m позиций в алфавитном порядке. Если значение m положительно, то смещение происходит в прямом направлении, если отрицательно — в обратном. Причем подразумевается, что смещение происходит циклически — за буквой «z» следует буква «a», в свою очередь, буква «z» следует перед буквой «a», если значение m отрицательно.

Ваша задача — по известным значениям n, m и слову, которое услышал последний гость в цепочке, восстановить слово, которое было изначально загадано Пашей.

Входные данные

Первая строка входных данных содержит два целых числа n и m — количество гостей на празднике и шаг смещения соответственно (1 ≤ n ≤ 105, - 25 ≤ m ≤ 25, m ≠ 0).

Вторая строка содержит слово, которое услышал последний гость из цепочки. Длина слова l удовлетворяет неравенству 1 ≤ l ≤ 103. Слово состоит только из строчных букв латинского алфавита.

Выходные данные

В единственной строке выходных данных необходимо вывести слово, которое загадал Паша.

Примеры
Стандартный вводСтандартный вывод
10 3
gifhswhg
accepted
129 -21
xiwxamxlrikexmudhmsdfdq
testwithnegativeinteger