Профессор Икс по утрам любит разгадывать загадки. Но очередная задача больному профессору оказалась не по зубам.
Профессор любит вводить необычные функции, особенно для строк. Примерами таких функций могут послужить G и F.
Подстрока — это строка, образованная из исходной путем удаления некоторого (возможно, нулевого) количества символов с начала и с конца строки. i-ый префикс — это строка, у которой удалили нулевое количество символов с начала и оставили ровно i символов всего. i-ый суффикс — это строка, у которой удалили нулевое количество символов с конца и ровно i - 1 с начала.
Для строки s Gi — это длина максимального суффикса i-ого префикса, который является префиксом строки s и не совпадает с самим i-м префиксом; Fi — это длина максимального префикса i-ого суффикса, который является префиксом строки s. G1 = 0 и F1 = 0, потому что так решил профессор, а с ним трудно спорить.
Назовем странностью строки сумму попарных произведений значений функции Gi и Fi от строки для i от 1 до |s|. Необходимо отыскать строку длины не более, чем m, странность которой равна заданному числу k.
При встрече с Росомахой он попросил у товарища помощи. Но и для героя эта загадка оказалась слишком сложной. Сможете ли вы решить ее?
В первой строке входного файла заданы числа k и m — странность и ограничение на длину строки, которую нужно создать (1 ≤ k ≤ 1014; значение m в каждой группе тестов фиксированное, см. раздел «Система оценки»).
Вывести строку из маленьких латинских букв длины не более m символов, странность которой равна k. Если возможных строк несколько, выведите любую. Гарантируется, что ответ существует.
Первая группа тестов состоит из тестов, для которых выполняются ограничения k ≤ 100, m = 25. Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Вторая группа тестов состоит из тестов, для которых выполняются ограничения k ≤ 105, m = 150. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 30 баллов.
Третья группа тестов состоит из тестов, для которых выполняются ограничения k ≤ 109, m = 2500. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 20 баллов.
Четвертая группа тестов состоит из тестов, для которых выполняются ограничения k ≤ 1014, m = 105. Баллы за эту группу начисляются только при прохождении всех тестов группы и всех предыдущих групп. Стоимость группы составляет 30 баллов.
Обратите внимание на возможность узнать результат проверки вашего решения на всех тестах, нажав на ссылку «Запросить информацию о проверке» на вкладке «Решения».
10 25
aaaab
Рассмотрим строку . Ее функция G = [0, 1, 2, 3] и F = [0, 3, 2, 1]. Таким образом, странность строки равна 0·0 + 1·3 + 2·2 + 3·1 = 10