Занятие 19

Однажды конструктор Трурль заглянул в гости к Клапауцию, и тот похвастался новым кодовым замком, стоящим на двери секретной лаборатории.

– Вот, смотри – на замке несколько кнопок с буквами. Можно нажимать кнопки сколько угодно – дверь не откроется, пока K (я установил K равным трем) последних нажатых букв не совпадут с правильной комбинацией. Буквы в этой комбинации не должны повторяться, так как в замок встроен специальный защитный механизм. Если среди любых K последних введенных букв есть хотя бы две одинаковые, то на мой пейджер поступает сообщение, что кто-то пытается открыть дверь, подбирая код.

Через несколько дней, когда Клапауций отправился на собрание Артели Свободных Механиков, Трурль проник в его дом, чтобы ознакомиться с новыми изобретениями Клапауция в его секретной лаборатории. Чтобы открыть кодовый замок нужно было всего лишь перебрать все комбинации, не вызвав тревоги. И следовало бы поторопиться, так как Клапауций мог явиться с собрания в любой момент.

Напишите программу, которая по количеству букв в комбинации для открытия кодового замка и количеству кнопок на замке определит минимальную последовательность нажатий кнопок замка, которая содержит все возможные комбинации и не вызывает тревоги.

В первой строке ввода содержатся два целых числа `K` и `N\ (1≤K≤N≤26,\ N^K≤60000)`, разделенных пробелом – количество букв в комбинации для открытия кодового замка и количество кнопок на замке. Кнопки обозначаются последовательными прописными латинскими буквами, начиная с А.

Вывести минимальную последовательность нажатий кнопок замка, содержащую все возможные комбинации. Если существует несколько вариантов, то вывести один (любой) из них. Если перебрать все комбинации без тревоги не удастся, то вывести сообщение "IMPOSSIBLE".

3 4

ABCABDACBACDBADCBDCADBCDAB