Description

Given a string S, you need to select a pair of characters from S to perform one swap (you must swap!!!!!!!!), and obtain the new string with the smallest lexicographical order! 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" has a smaller lexicographical order 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 ``` ## 目标

CodesOnline