A jeweler is restringing a broken necklace. The recovered beads come loose in a bag, and each bead is stamped with a lowercase letter from 'a' to 'z' indicating its color; beads of the same color are indistinguishable from one another.

The jeweler rebuilds the necklace one wave at a time. In a single wave: first, scanning colors from 'a' to 'z', for every color that still has at least one bead remaining in the bag, thread one bead of that color onto the necklace and remove it from the bag; then, scanning colors from 'z' back down to 'a', for every color that still has at least one bead remaining in the bag (after the first scan of this same wave), thread one more bead of that color onto the necklace and remove it. The jeweler repeats waves, one after another, until the bag is completely empty.

Given the bag's contents, reconstruct the exact sequence of bead colors that ends up threaded onto the necklace.

Input format

A single line containing a string s of lowercase English letters — the colors of the beads in the bag (their order in the input is irrelevant; only the count of each color matters).

Output format

A single line containing the necklace's bead colors, in the exact order they were threaded, as one string of the same length as s.

Constraints

• 1 <= |s| <= 2000
• s consists only of lowercase English letters ('a'-'z').

aabbccdd

abcddcba

leetcode

cdelotee