## UNICA - Unique Strings

no tags

Some people who love strings have decided to call a special group of strings as the “unique strings.”

Let’s define a(S) as the number of characters “a” the string S contains, and b(S) as the number of characters “b” the string S contains.

S is a unique string if:

1)      S only contains the characters “a” and “b”

2)      For every substring S’of S, | a(S’) – b(S’) | <= 3

For example, “abbab” is a unique string. However, “abbbba” is not because it includes the substring “bbbb” for which | a(“bbbb”) – b(“bbbbb”) | = 4 > 3.

Let’s say we sort the unique strings – first by length and then lexicographically. The Nth unique string is the string that appears in the position N in the sorted list. The first unique string is assigned the number 1.

The first 12 unique strings in the sorted list are: a, b, aa, ab,ba, bb, aaa, aab,  aba, abb, baa, bab

### Input

A single number N (1 <= N <= 1014). Your task is to find the Nth unique string in the sorted list.

### Output

A single line: the Nth unique string in the sorted list.

### Example

```Input:
10

Output:
abb```
`_______`
`Input:`
`19`
`Output:`
`abab`