Маркер в библиотеке

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

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

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