Alternate Digits and Letters

You are given a string s consisting only of alphanumeric characters (letters and digits). Your task is to rearrange the string so that letters and digits are alternated as evenly as possible. Specifically, if it is possible to interleave the characters in such a way that no two adjacent characters are of the same type, output one valid rearrangement; otherwise, output an empty string.

Note: The rearrangement should follow these rules:

• If the number of letters exceeds the number of digits, then the output should start with a letter.
• If the number of digits exceeds the number of letters, the rearrangement will naturally start with a digit.
• If the absolute difference between the number of letters and digits is more than 1 (i.e. \(|N_{letters} - N_{digits}| > 1\)), then it is impossible to rearrange without having two consecutive characters of the same type, so output an empty string.

For example:

• Input: a0b1c2 → Output: 0a1b2c
• Input: 123abc → Output: 1a2b3c
• Input: abcd → Output: (empty string)

inputFormat

The input consists of a single line containing the string s (1 ≤ |s| ≤ 100) composed of digits and English letters.

outputFormat

Output a single line containing the reformatted string. If no valid reformatting exists, output an empty string.

a0b1c2

0a1b2c