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

시간 제한1초메모리 제한1024 MB

요약

문자 하나를 골라 출력한 뒤 그 문자를 기준으로 나뉜 왼쪽과 오른쪽 부분에 같은 과정을 반복해 얻을 수 있는 문자열 가운데 사전순으로 가장 작은 것을 구한다.

난이도: 보통10점 중 7점
유형: 문자열, 그리디, 스택, 재귀
정답자: 아직 제출이 없습니다

문제

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

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

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

выбрать в $s$ некоторый символ $s\_i$ , после чего выписать его на бумагу;
разделить $s$ по этому символу на две части: $s\_l = \overline{s\_1 s\_2 \ldots s\_{i - 1}}$ и $s\_r = \overline{s\_{i + 1} s\_{i + 2} \ldots s\_n}$ ;
применить последовательно этот же алгоритм сначала к $s\_l$ , а потом к $s\_r$ .

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

입력

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

출력

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

예제2

예제 1
입력
```
bbaacc
```
예상 출력
```
aabbcc
```
예제 2
입력
```
abacaba
```
예상 출력
```
aaaabcb
```