Sort Letters and Digits

You are given a string s containing a mixture of lowercase letters and digits. Your task is to produce a new string in which all letters are sorted in alphabetical order and all digits are sorted in ascending numerical order, while the relative positions of letters and digits remain unchanged.

For example, consider the input "f4e3d2c1b0a9": the letters {f, e, d, c, b, a} when sorted yield {a, b, c, d, e, f} and the digits {4, 3, 2, 1, 0, 9} when sorted yield {0, 1, 2, 3, 4, 9}. Replacing each letter and digit in its original position with the corresponding sorted character gives the output "a0b1c2d3e4f9".

This problem tests your skill in string manipulation and sorting based on character classes. All formulas are expressed in LaTeX format when needed. For instance, the sorting process can be viewed as:

\(\text{result}[i] = \begin{cases}\text{sorted_letters}[j] & \text{if } s[i] \text{ is a letter} \\ \text{sorted_digits}[k] & \text{if } s[i] \text{ is a digit}\end{cases}\)

inputFormat

The input consists of a single line containing the string s. The string may be empty or contain up to 100,000 characters, and it will only include lowercase letters and digits.

outputFormat

Output the transformed string after sorting letters and digits separately while preserving their respective positions.## sample

a1b2c3

a1b2c3