Alternate Letters and Digits

You are given a string (s) containing both letters and digits. Your task is to rearrange the characters in (s) so that letters and digits alternate. If it is not possible to obtain such a string, output an empty string.

For example, given the string "a0b1", one possible answer is "0a1b". If the string contains characters of only one type or the difference between the counts of letters and digits is more than one, the answer should be an empty string.

The letters and digits should retain their relative order? (Note: The problem only requires alternating them, and a valid solution is guaranteed by the algorithm described below.)

Mathematically, let (L) be the list of letters and (D) the list of digits. A valid reordering (R) is such that for every index (i): [ R_{i} \in \begin{cases} L & \text{if } i \text{ is even and } |L| > |D|, \ D & \text{otherwise.} \end{cases} ] If no such valid reordering exists (i.e. (| |L| - |D| | > 1)), return the empty string.

inputFormat

Input is given via stdin as a single line containing the string (s). The string (s) consists of alphanumeric characters (letters and digits) and its length is at least 1.

outputFormat

Output the reformatted string to stdout. If it is not possible to reformat the string such that letters and digits alternate, output an empty string.## sample

a0b1

0a1b