Lexicographically Smallest String

Given a string \(S\), your task is to find the lexicographically smallest string that can be obtained by rearranging its characters. In other words, output the string when its characters are sorted in non-decreasing order.

Recall that a string \(T\) is lexicographically smaller than a string \(U\) if at the first position where \(T\) and \(U\) differ, the character in \(T\) comes before the character in \(U\) in the alphabet. Mathematically, if \(\pi(S)\) represents all permutations of \(S\), you need to determine the string \(T\) such that:

$$T = \min\{x : x \in \pi(S)\}$$

inputFormat

The input consists of a single line containing a string S composed of lowercase English letters.

outputFormat

Output the lexicographically smallest permutation of the string S.

bacd

abcd