24627번 - Подстроки и подпоследовательности 다국어

문제

Рассмотрим строку $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$-ю в соответствии с описанным в задаче упорядочением необычную строку.

제한

힌트