Beaking Spackwards

Time limit1sMemory limit1024 MB

Summary

Build a lowercase string of length at most 100000 that contains exactly s palindrome substrings, where s can be up to 1e9.

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

Problem

The 42nd meeting of the Fortnightly Palindrome Convention is coming up. For this special occasion, the members want to spend a session admiring a special kind of palindrome-esque words. These words do not have to be palindromes by themselves, but they must contain an exact, predetermined number of palindrome substrings. Your task is to generate these palindrome-esque words.

As an example, consider the second sample input. The output abacaba contains exactly $12$ palindrome substrings: the seven individual letters, two occurrences of aba (at the start and at the end), aca, bacab, and abacaba.

Input

The input consists of one line with an integer $s$ ( $1 \leq s \leq 10^9$ ), the number of required palindrome substrings.

Output

Output a string that contains exactly $s$ palindrome substrings. The string must have length between $1$ and $10^5$ characters (inclusive) and consist only of English lowercase letters (a-z). If there are multiple valid solutions, you may output any one of them.

Examples2

Example 1
Input
```
6
```
Expected output
```
abab
```
Example 2
Input
```
12
```
Expected output
```
abacaba
```