Dense Subsequence

题意翻译

### 题目描述 给定长度为n(1 <= n <= 100,000) 的字符串s，现在要求选取一些字符使得每个长度为m 的字符串区间均有一个被选中的字符，且选中的这些字符**重排列**后得到的字符串字典序最小 ### 输入格式 输入包括两行 第一行包括一个正整数m(1<=m<=100000) 意思如题目描述所示，第二行包括一段字符串s ### 输出格式 输出仅一行，为重排列后的选中字符串

题目描述

You are given a string $ s $ , consisting of lowercase English letters, and the integer $ m $ . One should choose some symbols from the given string so that any contiguous subsegment of length $ m $ has at least one selected symbol. Note that here we choose positions of symbols, not the symbols themselves. Then one uses the chosen symbols to form a new string. All symbols from the chosen position should be used, but we are allowed to rearrange them in any order. Formally, we choose a subsequence of indices $ 1<=i_{1}&lt;i_{2}&lt;...&lt;i_{t}<=|s| $ . The selected sequence must meet the following condition: for every $ j $ such that $ 1<=j<=|s|-m+1 $ , there must be at least one selected index that belongs to the segment $ [j, j+m-1] $ , i.e. there should exist a $ k $ from $ 1 $ to $ t $ , such that $ j<=i_{k}<=j+m-1 $ . Then we take any permutation $ p $ of the selected indices and form a new string $ s_{ip1}s_{ip2}...\ s_{ipt} $ . Find the lexicographically smallest string, that can be obtained using this procedure.

输入输出格式

输入格式

The first line of the input contains a single integer $ m $ ( $ 1<=m<=100000 $ ). The second line contains the string $ s $ consisting of lowercase English letters. It is guaranteed that this string is non-empty and its length doesn't exceed $ 100000 $ . It is also guaranteed that the number $ m $ doesn't exceed the length of the string $ s $ .

输出格式

Print the single line containing the lexicographically smallest string, that can be obtained using the procedure described above.

输入输出样例

输入样例 #1

3
cbabc

输出样例 #1

a

输入样例 #2

2
abcab

输出样例 #2

aab

输入样例 #3

3
bcabcbaccba

输出样例 #3

aaabb

说明

In the first sample, one can choose the subsequence $ {3} $ and form a string "a". In the second sample, one can choose the subsequence $ {1,2,4} $ (symbols on this positions are 'a', 'b' and 'a') and rearrange the chosen symbols to form a string "aab".