Задача №111266. ABBA или BABA?
У одного из меломанов, участвующих в подготовке этой олимпиады, любимой группой так и остаётся ABBA (да простят его некоторые участники, предпочитающие что-нибудь «потяжелее»). Соответственно, когда речь заходит о примерах различных алгоритмов на строках, он в первую очередь составляет строки из двух букв a и b.
Собственно из анализа таких примеров и родилась следующая задача. Пусть мы хотим прочитать в строке буквосочетание ab. При этом a и b не обязательно должны стоять подряд, достаточно, чтобы a встречалось в строке раньше, чем b. Как составить строку минимально возможной длины, чтобы это буквосочетание можно было прочитать ровно K способами? Например, в строке abba это буквосочетание можно прочитать дважды, но эта строка не будет самой короткой для K = 2, а в строке abab его можно прочитать три раза, и более короткую строку для K = 3 составить нельзя.
Напишите программу, которая и будет составлять подобную строку минимальной длины для заданного натурального K или будет определять, что сделать это невозможно.
Входные данные содержат только одно натуральное число K (1 ≤ K ≤ 109).
Выведите строку, удовлетворяющую условию задачи, или слово «Impossible», если искомую строку составить невозможно. Если искомых строк минимальной длины несколько, то выведите любую из них.
1
ab
3
abab