Жюри всероссийских зимних сборов школьников 2007-2008
Ограничение времени:
2 сек
Входной файл:
game.in
Ограничение памяти:
64 Мб
Выходной файл:
game.out
Максимальный балл:
100
Условие
Два игрока играют в следующую игру:
Дана строка.
Игроки по очереди стирают один символ с начала или конца строки, после чего дописывают его в конец результата.
Цель первого игрока состоит в том, чтобы результирующая строка была как можно больше (в лексикографическом порядке), а
цель второго — чтобы она была как можно меньше.
Определите полученный результат в предположении, что оба игрока играют оптимально.
Формат входного файла
В единственной строке входного файла записана строка, состоящая из строчных латинских букв, длиной
не более 100 символов.
Формат выходного файла
Выведите единственную строку — полученный результат при оптимальной игре обоих игроков.