На день рождения Пете подарили строку s длиной до 105 символов. Он взял еще две пустые строки t и u и решил сыграть в игру. По правилам в игре допускается два варианта ходов:
- Изъять символ из начала строки s и приписать его в конец строки t.
- Изъять символ из конца t и приписать его в конец строки u.
В результате Петя хочет, чтобы строка u была лексикографически минимальна, а s и t — пусты.
Напишите программу, которая поможет Пете выиграть в игру.
Выходные данные
Выведите полученную строку u.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
cab
|
abc
|
|
2
|
acdb
|
abdc
|