Подстроки и подпоследовательности

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