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$).

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