Рассмотрим строку $$$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