Unique Substrings

Time limit1sMemory limit256 MB

Summary

Build a lowercase string of length at most 4096 that has exactly K distinct substrings, where K is at most 2^22.

Level: Medium6 of 10
Topics: String, Greedy, Implementation
Solved: No attempts yet

Problem

Create a string $S_1S_2 \ldots S_N$ of $N$ lowercase letters, where $1 \le N \le 2^{12}$ . The string must have exactly $K$ distinct substrings.

A substring is a sequence of the form $S_L S_{L+1} \ldots S_{R-1} S_R$ for some $1 \le L \le R \le N$ . Two substrings are the same if they are the same sequence of letters.

Input

The first line contains one integer $K$ ( $1 \le K \le 2^{22}$ ). $N$ is not given. The string you create may have any length $N$ with $1 \le N \le 2^{12}$ .

Output

Print one line containing one string of $N$ lowercase letters, where $1 \le N \le 2^{12}$ . The string must have exactly $K$ distinct substrings. If several strings qualify, any of them is accepted. Under these constraints, such a string always exists.

Hint

For the first example, the 15 distinct substrings of banana are a, an, ana, anan, anana, b, ba, ban, bana, banan, banana, n, na, nan, and nana. Another string with 15 distinct substrings is aaaaaaaaaaaaaaa, which is also a correct output for the first example.

Examples2

Example 1
Input
```
15
```
Expected output
```
banana
```
Example 2
Input
```
351
```
Expected output
```
abcdefghijklmnopqrstuvwxyz
```