← 返回题目列表

Codeforces · 938/F

F. 删除子字符串

中文机器翻译题面 查看原题

给定一个字符串 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。