{"raw_statement":[{"iden":"statement","content":"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 2_i_ - 1 from _s_.\n\nPrint the lexicographically minimal string you may obtain after performing _k_ such operations."},{"iden":"input","content":"The only line contains one string _s_ consisting of _n_ lowercase Latin letters (1 ≤ _n_ ≤ 5000)."},{"iden":"output","content":"Print the lexicographically minimal string you may obtain after performing _k_ operations."},{"iden":"examples","content":"Input\n\nadcbca\n\nOutput\n\naba\n\nInput\n\nabacabadabacaba\n\nOutput\n\naabacaba"},{"iden":"note","content":"Possible operations in examples:\n\n1.  adcb**c**a a**dc**ba aba;\n2.  ab**a**cabadabacaba a**bc**abadabacaba aaba**daba**caba aabacaba."}],"translated_statement":[{"iden":"statement","content":"给定一个字符串 #cf_span[s]，初始时由 #cf_span[n] 个小写拉丁字母组成。之后，你对它执行 #cf_span[k] 次操作，其中 。在第 #cf_span[i] 次操作中，你*必须*删除 #cf_span[s] 中一个长度恰好为 #cf_span[2i - 1] 的子串。\n\n输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。\n\n唯一的一行包含一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ n ≤ 5000]）。\n\n请输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。\n\n示例中的可能操作：\n\n"},{"iden":"input","content":"唯一的一行包含一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]（#cf_span[1 ≤ n ≤ 5000]）。"},{"iden":"output","content":"请输出经过 #cf_span[k] 次操作后可能得到的字典序最小的字符串。"},{"iden":"examples","content":"输入\nadcbca\n输出\naba\n输入\nabacabadabacaba\n输出\naabacaba"},{"iden":"note","content":"示例中的可能操作：\nadcb*c*a → a*dc*ba → aba；\nab*a*cabadabacaba → a*bc*abadabacaba → aaba*daba*caba → aabacaba。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ s \\in \\Sigma^n $ be the initial string, where $ \\Sigma = \\{a, b, \\dots, z\\} $ and $ n \\in \\mathbb{Z}^+ $, $ 1 \\le n \\le 5000 $.  \nLet $ k \\in \\mathbb{Z}^+ $ be the number of operations, where $ k = \\left\\lfloor \\frac{n}{2} \\right\\rfloor $.  \nFor each operation $ i \\in \\{1, \\dots, k\\} $, you must remove a contiguous substring of length $ 2i - 1 $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 5000 $  \n2. For each operation $ i \\in \\{1, \\dots, k\\} $, the substring removed has length $ 2i - 1 $.  \n3. After $ k $ operations, the remaining string has length $ n - \\sum_{i=1}^k (2i - 1) = n - k^2 \\ge 0 $.  \n\n**Objective**  \nFind the lexicographically minimal string obtainable after performing exactly $ k $ operations, each removing a substring of length $ 2i - 1 $ in the $ i $-th step.","simple_statement":null,"has_page_source":false}