← 返回题目列表

Codeforces · 724/D

D. 密集子序列

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

给定一个字符串 s,由小写英文字母和整数 m 组成。

人们应该从给定的字符串中选择一些符号,以便长度为 m 的任何连续子段都至少有一个选定的符号。请注意,这里我们选择符号的位置,而不是符号本身。

然后使用所选符号形成一个新字符串。应使用所选位置的所有符号,但我们可以按任何顺序重新排列它们。

形式上,我们选择索引 1 ≤ i1 < i2 < ... < it ≤ |s| 的子序列。所选序列必须满足以下条件:对于每个 j ,使得 1 ≤ j ≤ |s| - m + 1,必须至少有一个选定的索引属于段 [j, j + m - 1],即从 1 到 t 应该存在一个 k,使得 j ≤ ik ≤ j + m - 1。

然后我们对所选索引进行任意排列 p 并形成一个新字符串 sip1sip2... sipt。

查找可以使用此过程获得的字典顺序最小的字符串。

输入

输入的第一行包含一个整数 m (1 ≤ m ≤ 100 000)。

第二行包含由小写英文字母组成的字符串 s。保证该字符串非空且长度不超过100 000。还保证数字m不超过字符串s的长度。

输出

打印包含字典顺序最小字符串的单行,该字符串可以使用上述过程获得。

示例

输入 #1

3
cbabc

输出 #1

a

输入 #2

2
abcab

输出 #2

aab

输入 #3

3
bcabcbaccba

输出 #3

aaabb

注意

在第一个示例中,可以选择子序列 {3} 并形成字符串“a”。

在第二个示例中,可以选择子序列 {1, 2, 4}(该位置上的符号为“a”、“b”和“a”)并重新排列所选符号以形成字符串“aab”。