Zig Zag Nametag

Interview

Time limit1sMemory limit256 MB

Summary

Given k, print the shortest lowercase string with adjacent letter differences summing to k, smallest alphabetically on ties.

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

Problem

Ninjas wear fake nametags when they go to conferences. One of them wants to impress his teacher. The teacher picks a new favorite number every day, and the pupil wants to encode that number in the name on his nametag.

The name consists of lower case letters only. Each letter takes its position in the alphabet as its value, so a is $1$ , b is $2$ , and z is $26$ . The value of a string is the sum of the absolute differences of every consecutive pair of letters. For example, the string azxb has this value:

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

The name on the nametag is the shortest string whose value equals the teacher's favorite number. If several shortest strings exist, the ninja picks the one that comes first alphabetically.

Given the teacher's favorite number $k$ , find the name that the ninja should put on the nametag.

Input

The first line contains one integer $k$ ( $1 \le k \le 1\,000\,000$ ), the teacher's favorite number.

A name that satisfies the condition always exists.

Output

Print the name that the ninja should put on the nametag, written in lower case letters, on the first line.

Examples3

Example 1
Input
```
1
```
Expected output
```
ab
```
Example 2
Input
```
19
```
Expected output
```
at
```
Example 3
Input
```
77
```
Expected output
```
aoazb
```