Beaking Spackwards

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

요약

길이가 100000 이하인 소문자 문자열을 만들어 팰린드롬 부분 문자열의 개수가 정확히 s가 되도록 한다.

난이도: 보통10점 중 6점
유형: 문자열, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

The 42nd meeting of the Fortnightly Palindrome Convention is coming up, and for this special occasion, they want to spend a session admiring a special kind of palindrome-esque words. These words are not necessarily a palindrome by themselves, but they should contain an exact, predetermined number of palindrome substrings. As preparation for the session, 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 times aba (at the start and at the end), aca, bacab, and abacaba.

입력

The input consists of:

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

출력

Output a string that contains exactly $s$ palindrome substrings. This string should have length between $1$ and $10^5$ characters (inclusive) and only consists of English lowercase letters (a-z).

If there are multiple valid solutions, you may output any one of them.

예제2

예제 1
입력
```
6
```
예상 출력
```
abab
```
예제 2
입력
```
12
```
예상 출력
```
abacaba
```