Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
Недавно Петя научился определять, является ли счастливой строка из маленьких букв латинского алфавита. Для каждой буквы в отдельности выписываются в порядке возрастания все ее позиций в строке. В итоге получается 26 списков чисел, некоторые из них могут быть пусты. Строка считается счастливой тогда и только тогда, когда в каждом списке модуль разности любых двух соседних чисел является счастливым числом.
Например, рассмотрим строку «zbcdzefdzc». Списки позиций одинаковых символов:
- b: 2
- c: 3, 10
- d: 4, 8
- e: 6
- f: 7
- z: 1, 5, 9
- Списки позиций букв a, g, h, ..., y пусты.
Эта строка счастливая, так как все разности являются счастливыми числами. Для символа z: 5 - 1 = 4, 9 - 5 = 4, для символа c: 10 - 3 = 7, для символа d: 8 - 4 = 4.
Заметим, что если какой-то символ встречается в строке только один раз, то после построения списков позиций на счастливость строки он уже не влияет. Строка, в которой нет повторяющихся символов, является счастливой.
Найдите лексикографически минимальную счастливую строку длины n.
Примечание
Лексикографическое сравнение строк реализует оператор < в современных языках программирования. Строка a лексикографически меньше строки b, если существует такое i (1 ≤ i ≤ n), что ai < bi, а для любого j (1 ≤ j < i) aj = bj.