给定一个字符串 s,最初由 n 个小写拉丁字母组成。之后,您对其执行 k 次操作,其中 $$k = \left\lfloor \log_2(n) \right\rfloor$$。在第 i 次操作期间,您必须从 s 中删除一些长度恰好为 2i - 1 的子字符串。
打印执行 k 个这样的操作后可能获得的按字典顺序排列的最小字符串。
输入
唯一一行包含一个由 n 个小写拉丁字母 (1 ≤ n ≤ 5000) 组成的字符串 s。
输出
打印执行 k 次操作后可能获得的按字典顺序排列的最小字符串。
示例
输入 #1
adcbca
输出 #1
aba
输入 #2
abacabadabacaba
输出 #2
aabacaba
注意
示例中可能的操作:
1. adcbca $$\rightarrow$$ adcba $$\rightarrow$$ aba;
2. abacabadabacaba $$\rightarrow$$ aabadabacaba $$\rightarrow$$ aabadabacaba $$\rightarrow$$ aabacaba。