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

Дана строка s, изначально состоящая из n строчных латинских букв. Над ней производятся k операций, где . В i-ю операцию необходимо удалить некоторую подстроку длиной ровно 2i - 1 из s.

Выведите лексикографически минимальную строку, которую возможно получить после выполнения k операций.

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

Единственная строка содержит строку s из n строчных латинских букв (1 ≤ n ≤ 5000).

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

Выведите лексикографически минимальную строку, которую можно получить после выполнения k операций.

Примеры
Входные данные
adcbca
Выходные данные
aba
Входные данные
abacabadabacaba
Выходные данные
aabacaba
Примечание

Возможные операции в примерах:

  1. adcbca adcba aba;
  2. abacabadabacaba abcabadabacaba aabadabacaba aabacaba.