题目描述

给定一个字符串 $S$，找到通过对 $S$ 中的字符进行排列而得到的字典序最小的字符串 $S'$。

对于两个不同的字符串 $s = s_1 s_2 \\ldots s_n$ 和 $t = t_1 t_2 \\ldots t_m$，当满足以下条件之一时，我们称 $s$ 字典序小于 $t$。

• 存在整数 $i\\ (1 \\leq i \\leq \\min(n,m))$，使得 $s_i \\lt t_i$ 并且对于所有的整数 $j\\ (1 \\leq j \\lt i)$，有 $s_j=t_j$。
• 对于所有的整数 $i\\ (1 \\leq i \\leq \\min(n,m))$，有 $s_i = t_i$，并且 $n \\lt m$。

约束条件

• $S$ 是一个由小写英文字母组成的长度在 $1$ 到 $2 \\times 10^5$ 之间（包括边界）的字符串。

输入

从标准输入读入数据，输入格式如下：

$S$

输出

打印通过对 $S$ 中的字符进行排列而得到的字典序最小的字符串 $S'$。

示例输入1

aba

示例输出1

aab

通过对 aba 进行排列，可以得到以下三个字符串：

• aba
• aab
• baa

其中字典序最小的是 aab。

示例输入2

zzzz

示例输出2

zzzz