Вам дається рядок \(S\). Знайдіть лексикографічно найменший рядок \(S'\) отриманий шляхом перестановки \(C\) символів.

Тут для двох різних рядків \(s = s_1 s_2 \ldots s_n\) і \(t = t_1 t_2 \ldots t_m\), \(s \lt t\) виконується лексикографічно, коли виконується одна з наведених нижче умов.

• Існує ціле число \(i\) (\(1 \leq i \leq \min(n,m)\)) таке, що \(s_i \lt t_i\) і \(s_j=t_j\) для всіх цілих чисел \(j\) (\(1 \leq j \lt i\)).

• \(s_i = t_i\) для всіх цілих чисел \(i\) (\(1 \leq i \leq \min(n,m)\)) і \(n \lt m\).

Обмеження

\(S\) — це рядок довжиною від 1 до \(2 \times 10^5\) (включно), що складається з малих англійських літер.

Формат вхідних даних

Вхідний потік містить рядок \(S\) (\(1 \le |S| \le 2 \times 10^5\))

Формат вихідних даних

У вихідний потік виведіть шуканий рядок.

Примітка

До прикладу 1:

Три рядки можна отримати шляхом перестановки aba:

• аbа

• aab

• bаа

Лексикографічно найменший серед них ааb.

Приклад вхідних даних

aba

Приклад вихідних даних

aab

Приклад вхідних даних

zzzz

Приклад вихідних даних

zzzz