C. Минимальная строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На день рождения Пете подарили строку s длиной до 105 символов. Он взял еще две пустые строки t и u и решил сыграть в игру. По правилам в игре допускается два варианта ходов:

  • Изъять символ из начала строки s и приписать его в конец строки t.
  • Изъять символ из конца t и приписать его в конец строки u.

В результате Петя хочет, чтобы строка u была лексикографически минимальна, а s и t — пусты.

Напишите программу, которая поможет Пете выиграть в игру.

Входные данные

В единственной строке задана непустая строка s (1 ≤ |s| ≤ 105), состоящая из строчных латинских букв.

Выходные данные

Выведите полученную строку u.

Примеры
Входные данные
cab
Выходные данные
abc
Входные данные
acdb
Выходные данные
abdc