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