Description

Given a string S, you need to select a pair of characters from S to perform one swap (you must swap!!!!!!), and make the resulting new string lexicographically smallest! For example: S = "abacc". If you swap characters 1(a) and 4(c), you get the string "cbaac". If you swap characters 2(a) and 3(b), you get the string "aabcc". Among these: "aabcc" is lexicographically smaller than "cbaac". Moreover, "aabcc" is the smallest lexicographical string among all possible swap methods. Another example: S = "aaab". Swapping positions 1 and 2 or positions 1 and 3 both result in the string "aaab", and "aaab" is the smallest lexicographical string among all possible swap methods. Output this lexicographically smallest string.

Input Format

A string S (S consists only of lowercase characters from a to z, 2 <= length of S <= 500000).

Output Format

The lexicographically smallest new string.

```input1 abacc ``` ```output1 aabcc ``` ```markdown ## Source

CodesOnline

The translation preserves the original markdown heading format (`##`) and the content "CodesOnline" exactly as it appears in the source. No additional changes were made to the structure or formatting.