494. Longest Happy String

0

Medium

Alice has a fondness for the characters 'a', 'b', and 'c'. She defines a string s as being 'happy' if it meets the following criteria:
s consists only of the letters 'a', 'b', and 'c'.
s does not contain any instances of the substrings "aaa", "bbb", or "ccc".
s contains at most a occurrences of the letter 'a'.
s contains at most b occurrences of the letter 'b'.
s contains at most c occurrences of the letter 'c'.
Alice is seeking your assistance in finding the longest possible 'happy' string given three integers a, b, and c. If there are multiple longest 'happy' strings, you should return the lexicographically smallest string. If no such string exists, return an empty string "".
A substring is defined as a contiguous sequence of characters within a string.

Input Format

The first line of the input should contain three integers a, b, and c, representing the number of 'a', 'b', and 'c' respectively.

Output Format

You should return the largest possible lexicographically smallest 'happy' string.

Example

Input

1 1 7

Output

ccaccbcc

Constraints

0 <= a, b, c <= 100

a + b + c > 0

a + b + c > 0

Loading...

View Submissions

Console