28551번 - Маркер в библиотеке 다국어

문제

После того, как Джон Уик был объявлен экскомьюникадо, у него оставался всего лишь час, прежде чем за его голову официально будет выставлена награда. За этот час ему было необходимо собрать все, что может помочь ему выжить.

В Нью-Йоркской библиотеке в одной из книг Джон хранит Маркер и еще несколько предметов, которые могут помочь ему выбраться из ситуации. Чтобы найти эту книгу, Джону необходимо вспомнить ее библиотечный номер --- строку из маленьких латинских букв длины $n$.

У Джона записана подсказка $s,ドル которая может помочь ему вспомнить номер. Он помнит, что номер можно получить из $s$ следующим алгоритмом:

1. выбрать в $s$ некоторый символ $s_i,ドル после чего выписать его на бумагу;
2. разделить $s$ по этому символу на две части: $s_l = \overline{s_1 s_2 \ldots s_{i - 1}}$ и $s_r = \overline{s_{i + 1} s_{i + 2} \ldots s_n}$;
3. применить последовательно этот же алгоритм сначала к $s_l,ドル а потом к $s_r$.

Известно, что библиотечный номер книги --- это лексикографически минимальная из строк, которые можно получить из $s$ описанным образом. Помогите Джону его восстановить.

입력

В единственной строке ввода дана сама строка $s$ из маленьких латинских букв --- подсказка к библиотечному номеру книги (1ドル \leqslant |s| \leqslant 2 \cdot 10^5$).

출력

Выведите искомый библиотечный номер книги.

제한

힌트