UNICA - Unique Strings

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(“bbbb”) | = 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

Added by:Angel Paredes
Date:2012-02-13
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Cuban Olympiad in Informatics 2011 - Day 2 Problem A

hide comments
2014-11-09 15:07:40 Raju
IO from AC solution:

52
bbabb

60
aababb

70
ababbb

100
aaababb

102
aaabbab

150
bababaa

225
abbaaaba

500
bbaabbbab

1000
aabbabaaabb

2569
aaababbaababb

10000
babaaabbbaaabba

100005
ababaaababbabaababba

1234567
abbaabababaababbabababbaa

12345678
aabbabbaaabbababbaababbaaababa

87654321
abaababaabbabbaaabbabbabaababaabbb

100000000
abbbaaabbaabababbabbaababbaabbabab

9999999999
aabababaababbbaababbabaaabbbaabbaaabbbaabbab

10000000000
aabababaababbbaababbabaaabbbaabbaaabbbabaaab

100000000006
bbaabababbabaabaabababbaabbaabbababbaabaabbaabbb

9999999999990
ababbbabaabaabbabaabbbabaaabbaabbbaabbaaabbaabbbaabaabbaba

100000000000000
aabbbaabbaaabbbaaabbabaabbabbabaabaababbbaabbaabbaabbabaabbabaa



Last edit: 2014-11-09 15:08:12
2012-03-26 21:12:30 Nikolay Nedelchev
123456
babababbaaababbbabaa

987654321
abaababbbabaabbaaabbbaababbababaaabbbab

65536
abbaabababaababbaab
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.