지그재그 이름표

면접 대비

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

요약

k가 주어지면 인접한 글자 값 차이의 합이 k가 되는 가장 짧은 소문자 문자열을 사전 순으로 가장 앞선 것으로 출력합니다.

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

문제

닌자들은 학회에 갈 때 가짜 이름표를 단다. 그중 한 닌자는 스승에게 잘 보이고 싶어 한다. 스승은 날마다 좋아하는 수를 새로 정하고, 제자는 그 수를 이름표의 이름에 담으려 한다.

이름은 소문자 알파벳으로만 이루어진다. 각 글자에는 알파벳에서의 순서를 값으로 매긴다. 즉 a는 $1$ , b는 $2$ , 이런 식으로 z는 $26$ 이다. 문자열의 값은 이웃한 두 글자의 값 차이의 절댓값을 모두 더한 수다. 예를 들어 문자열 azxb의 값은 다음과 같다.

$|a - z| + |z - x| + |x - b| = |1 - 26| + |26 - 24| + |24 - 2| = 49$

닌자가 이름표에 적을 이름은 값이 스승이 좋아하는 수와 같은 문자열 중 가장 짧은 것이다. 가장 짧은 문자열이 여럿이면 그중 사전순으로 가장 앞서는 것을 고른다.

스승이 좋아하는 수 $k$ 가 주어질 때, 닌자가 이름표에 적어야 할 이름을 구하라.

입력

첫째 줄에 스승이 좋아하는 수 $k$ ( $1 \le k \le 1\,000\,000$ )가 하나 주어진다.

조건을 만족하는 이름은 항상 존재한다.

출력

첫째 줄에 닌자가 이름표에 적어야 할 이름을 소문자 알파벳으로 출력한다.

예제3

예제 1
입력
```
1
```
예상 출력
```
ab
```
예제 2
입력
```
19
```
예상 출력
```
at
```
예제 3
입력
```
77
```
예상 출력
```
aoazb
```