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(“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

hide comments
Raju: 2014-11-09 15:07:40

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
Nikolay Nedelchev: 2012-03-26 21:12:30

123456
babababbaaababbbabaa

987654321
abaababbbabaabbaaabbbaababbababaaabbbab

65536
abbaabababaababbaab


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