最小字典序排列

题目描述

给定一个字符串 $S$。求通过重排 $S$ 中的字符得到的字符串中,字典序最小的字符串 $S'$。

这里,对于两个不同的字符串 $s = s_1 s_2 \ldots s_n$ 和 $t = t_1 t_2 \ldots t_m$,当满足下列条件之一时,称 $s \lt t$(即 $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

输出格式

输出通过重排 $S$ 中的字符得到的字符串中字典序最小的字符串 $S'$。

样例

aba

aab

通过重排 aba 可以得到三个字符串:

• aba
• aab
• baa

其中字典序最小的是 aab。

zzzz

zzzz

数据范围

• $S$ 是由小写英文字母组成的字符串,长度为 $1$ 到 $2 \times 10^5$(含)。