102421: [AtCoder]ABC242 B - Minimize Ordering

Problem Statement

You are given a string $S$. Find the lexicographically smallest string $S'$ obtained by permuting the characters of $S$.

Here, for different two strings $s = s_1 s_2 \ldots s_n$ and $t = t_1 t_2 \ldots t_m$, $s \lt t$ holds lexicographically when one of the conditions below is satisfied.

• There is an integer $i\ (1 \leq i \leq \min(n,m))$ such that $s_i \lt t_i$ and $s_j=t_j$ for all integers $j\ (1 \leq j \lt i)$.
• $s_i = t_i$ for all integers $i\ (1 \leq i \leq \min(n,m))$, and $n \lt m$.

Constraints

• $S$ is a string of length between $1$ and $2 \times 10^5$ (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

$S$

Output

Print the lexicographically smallest string $S'$ obtained by permuting the characters in $S$.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

问题描述

你有一个字符串$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