410556: GYM104049 H Alluring Alloy

Allie is making an alluring amalgamation of aluminum, actinium, and all other alloys!

The recipe for creating an alloy can be represented by a string of lowercase letters, where each letter denotes a metal. Allie is fulfilling such a recipe. However, she has a quota to meet by 11 pm tonight, so she wants to use more metals than the recipe calls for.

Allie knows that you can add twice as much metal at any point and the resulting alloy will be unchanged. That is, you can duplicate any original letter (leaving both copies of the letter in the same place) without changing the result of the recipe. Note that you can only duplicate an original letter once, and you cannot duplicate existing duplicates.

What's the lexicographically smallest string that can be created by applying the above operation any number of times?

The first line contains a single string ($$$1 \le |S| \le 10^6$$$), denoting the alloy recipe. Each character in $$$S$$$ will be a lowercase English letter.

Output a single string, the lexicographically smallest string that can be created by duplicating any original letters at most once.

silversurfer

siillveerrssurfeer