Подстроки и подпоследовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Рассмотрим строку $$$T$$$, составленную из строчных букв английского алфавита, и построим два множества: множество $$$S_1$$$ всех различных подстрок строки $$$T$$$ и множество $$$S_2$$$ всех различных подпоследовательностей строки $$$T$$$.

Например, для строки «icpc» $$$S_1$$$ cостоит из пустой строки, «i», «c», «p», «ic», «cp», «pc», «icp», «cpc» и «icpc». В $$$S_2$$$, помимо этих строк, входят строки «ip», «cc», «ipc» и «icc».

Назовём строку необычной, если $$$S_1=S_2$$$. Отсортируем все необычные строки по возрастанию длины, а строки равной длины — в лексикографическом порядке. Ваша задача — найти $$$n$$$-ю необычную строку.

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

Входные данные содержат одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$).

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

Выведите $$$n$$$-ю в соответствии с описанным в задаче упорядочением необычную строку.

Примеры

Входные данные
1
Выходные данные
a
Входные данные
27
Выходные данные
aa