Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

F. Erasing Substrings
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

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.

Examples
Input
adcbca
Output
aba
Input
abacabadabacaba
Output
aabacaba
Note

Possible operations in examples:

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