题目背景

翻译自「AtCoder ABC 242B」

题目描述

给定一个字符串 $S$。找出通过重新排列 $S$ 中的字符得到的字典序最小的字符串 $S'$。

这里，对于两个不同的字符串 $s=s_1s_2\cdots s_n$ 和 $t=t_1t_2\cdots t_n$，当满足以下条件之一时，$s<t$ 在字典序上成立：

• 存在一个整数 $i(1\le i\le \min(n,m))$ 使得 $s_i<t_i$ 且对于所有整数 $j(1\le j<i)$ 都有 $s_j=t_j$。

• 对于所有整数 $i(1\le i\le \min(n,m))$ 都有 $s_i=t_i$ 且 $n<m$。

输入格式

一行一个字符串 $S$。

输出格式

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

样例

aba

aab

zzzz

zzzz

说明/提示

样例 1 解释

通过重新排列 aba 可以得到三个字符串：

• aba
• aab
• baa

其中字典序最小的是 aab

数据范围

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