题目描述

给出一个字符串 $S$，你需要从 $S$ 中挑选一对字符进行一次交换（不可以不交换），并让得到的新字符串字典序最小。

例如：$S = \texttt{abacc}$，如果交换字符 $1$（a）和 $4$（c），得到字符串 $\texttt{cbaac}$；如果交换字符 $2$（a）和 $3$（b），得到字符串 $\texttt{aabcc}$。其中 $\texttt{aabcc}$ 的字典序小于 $\texttt{cbaac}$，并且 $\texttt{aabcc}$ 是所有交换方法中字典序最小的。

又如：$S = \texttt{aaab}$，则交换任意两个字符得到的字符串都是 $\texttt{aaab}$，且 $\texttt{aaab}$ 是所有交换方法中字典序最小的。

输出这个字典序最小的字符串。

输入格式

输入一个字符串 $S$（$S$ 只包含小写字母 $a$ 到 $z$）。

输出格式

输出字典序最小的新字符串。

样例

abacc

aabcc

数据范围与提示

$2 \le |S| \le 5 \times 10^5$

来源

CodesOnline