题目描述

给定一个长度为 $n$ 的字符串（仅包含小写英文字母），需要将其划分成 $k$ 个连续的非空子串。

对于划分后的第 $i$ 段子串，定义 $C_i$ 为该段中字典序最大的子串（子串为原段中连续的字符序列）。要求在所有合法的划分方案中，找到使得 $C_1, C_2, ..., C_k$ 中字典序最大的那个值 最小化 的方案，最终输出这个最小化的最大值字符串。

输入格式

1. 第一行输入一个正整数 $k$，表示划分的段数；
2. 第二行输入一个仅包含小写英文字母的字符串。

输出格式

输出一行字符串，代表满足条件的最小化最大值字符串。

样例输入 1

2
aba

样例输出 1

b

样例输入 2

4
acgtgtcgactgaacttcctatcctgg

样例输出 2

tgaact

数据范围与提示

• 字符串长度 $n$ 和划分段数 $k$ 满足 $1 \leq k \leq n \leq 400000$；
• 字典序比较规则：从左到右逐个字符比较，第一个不同字符的 ASCII 码值越大，对应字符串字典序越大；若前缀完全相同，长度更长的字符串字典序更大。