Erasing Substrings
Description
You are given a string s, initially consisting of n lowercase Latin letters. After that, you perform k operations with it, where 
. During i-th operation you must erase some substring of length exactly 2i - 1 from s.
Print the lexicographically minimal string you may obtain after performing k such operations.
The only line contains one string s consisting of n lowercase Latin letters (1 ≤ n ≤ 5000).
Print the lexicographically minimal string you may obtain after performing k operations.
Input
The only line contains one string s consisting of n lowercase Latin letters (1 ≤ n ≤ 5000).
Output
Print the lexicographically minimal string you may obtain after performing k operations.
Samples
adcbca
aba
abacabadabacaba
aabacaba
Note
Possible operations in examples:
- adcbca
adcba 
aba; - abacabadabacaba
abcabadabacaba 
aabadabacaba 
aabacaba.