Erasing Substrings

1000ms

262144K

Description:

You are given a string s, initially consisting of n lowercase Latin letters. After that, you perform k operations with it, where $\text{[math]}$ . During i-th operation you must erase some substring of length exactly 2^i - 1 from s.

Print the lexicographically minimal string you may obtain after performing k such 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.

Sample Input:

adcbca

Sample Output:

aba

Sample Input:

abacabadabacaba

Sample Output:

aabacaba

Note:

Possible operations in examples:

adcbca $\text{[math]}$ adcba $\text{[math]}$ aba;
abacabadabacaba $\text{[math]}$ abcabadabacaba $\text{[math]}$ aabadabacaba $\text{[math]}$ aabacaba.

Informação

Provedor Codeforces

Código CF938F