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

문제

Рассмотрим строку $TT$, составленную из строчных букв английского алфавита, и построим два множества: множество $S_{1}S\_1$ всех различных подстрок строки $TT$ и множество $S_{2}S\_2$ всех различных подпоследовательностей строки $TT$.

Например, для строки <<icpc>> $S_{1}S\_1$ cостоит из пустой строки, <<i>>, <<c>>, <<p>>, <<ic>>, <<cp>>, <<pc>>, <<icp>>, <<cpc>> и <<icpc>>. В $S_{2}S\_2$, помимо этих строк, входят строки <<ip>>, <<cc>>, <<ipc>> и <<icc>>.

Назовём строку необычной, если $S_1=S_{2}S\_1=S\_2$. Отсортируем все необычные строки по возрастанию длины, а строки равной длины --- в лексикографическом порядке. Ваша задача --- найти $nn$-ю необычную строку.

입력

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

출력

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