Lexicographically Smallest String

You are given a string s consisting of lowercase English letters (possibly empty). You can perform the following operation any number of times: choose any substring of s and reverse it. Your task is to find the lexicographically smallest string that can be obtained after performing any number of these operations.

Observation: It turns out that by performing sufficiently many substring reversals, one can effectively sort the characters of the string in non-decreasing order. In other words, the answer is the string with its characters in sorted order, i.e., \[ \text{answer} = \text{sorted}(s)\]

Examples:

• Input: bcda → Output: abcd
• Input: gfdca → Output: acdfg
• Input: aabb → Output: aabb

inputFormat

The input consists of a single line read from standard input (stdin) containing the string s. The string may be empty or consist solely of lowercase English letters.

outputFormat

Output the lexicographically smallest string that can be obtained by performing any number (including zero) of substring reversal operations on the input string. The output should be printed to standard output (stdout).

bcda

abcd