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

시간 제한1초메모리 제한512 MB

요약

서로 다른 부분 문자열의 집합과 서로 다른 부분 수열의 집합이 같은 문자열을 길이순, 사전순으로 정렬했을 때 n번째 문자열을 구한다.

난이도: 보통10점 중 7점
유형: 조합론, 문자열
정답자: 아직 제출이 없습니다

문제

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

예제2

예제 1
입력
```
1
```
예상 출력
```
a
```
예제 2
입력
```
27
```
예상 출력
```
aa
```