( ext{Description})
( ext{Solution})
先开始又想了个 ( ext{nt}) ( ext{DP})：(f[i][j]) 表示前 (i) 个字符划分成 (j) 段的最小字典序。但是这样根本无法转移，因为需要维护区间最大值，而且会面临某个后缀被切割后字典序的变化。
不妨直接二分答案子串的字典序。至于子串的种类数就是这个东西（先求出后缀的所有前缀数，再减去与之前重复的）：
[sum_{i=1}^n n-sa[i]+1-h[i]
]
计算 (L,R) 分别是枚举的子串的第一个字符下标（就是这个子串属于的后缀下标），这个子串结 (su) 的下标。
我们贪心地从后面往前面切（下面有张示意图，看完应该就懂了，其实就是字符串和数的优先级问题，和朴素基数排序和后缀数组的区别差不多）。
串：bc
前：abca
后：abc|a
如何 ( ext{check})？
如果第一位就有大于自己的，那么我肯定不会是答案（毕竟不能把单个点切了吧）。
如果判定字典序大于自己，就把它切了。
如何判定详见代码。
( ext{Code})
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int lim,n,m=122,c[maxn],x[maxn],y[maxn],num,sa[maxn],h[maxn],rk[maxn],L,R,ansl,ansr,lg[maxn],f[maxn][22];
char s[maxn];
void Suffix() {
rep(i,1,n) ++c[x[i]=s[i]];
rep(i,2,m) c[i]+=c[i-1];
fep(i,n,1) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1) {
num=0;
rep(i,n-k+1,n) y[++num]=i;
rep(i,1,n) if(sa[i]>k) y[++num]=sa[i]-k;
rep(i,1,m) c[i]=0;
rep(i,1,n) ++c[x[i]];
rep(i,2,m) c[i]+=c[i-1];
fep(i,n,1) sa[c[x[y[i]]]--]=y[i],y[i]=0;
swap(x,y);
x[sa[1]]=num=1;
rep(i,2,n)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
m=num;
}
}
void LCP() {
int k=0;
rep(i,1,n) rk[sa[i]]=i;
rep(i,1,n) {
if(rk[i]==1) continue;
if(k) --k;
int j=sa[rk[i]-1];
while(j+k<=n&&i+k<=n&&s[j+k]==s[i+k]) ++k;
h[rk[i]]=k;
}
}
void init() {
rep(i,2,n) lg[i]=lg[i>>1]+1;
rep(i,1,n) f[i][0]=h[i];
rep(j,1,20) rep(i,1,n) {
if(i+(1<<j)-1>n) break;
f[i][j]=Min(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
void Get(ll x) {
rep(i,1,n)
if(x>n-sa[i]+1-h[i]) x-=n-sa[i]+1-h[i];
else {L=sa[i],R=sa[i]+h[i]-1+x; return;}
}
int lcp(int x,int y) { // h[x] 是 x 与 x-1 的 LCP，所以只能算 [x+1,y] 区间
if(x==y) return n-sa[x]+1; // 特判相等的情况
if(x>y) swap(x,y);
int dis=lg[y-x];
return Min(f[x+1][dis],f[y-(1<<dis)+1][dis]);
}
bool Cmp(int a,int b,int c,int d) {
int l1=b-a+1,l2=d-c+1,dis=lcp(rk[a],rk[c]);
if(dis>=l1) return l1<=l2; // 这两个 if 的顺序不能调换
// 如果别人家的区间还没有别人家代表后缀和自己的代表后缀的 LCP 大，就直接比较两串长度
if(dis>=l2) return 0;
return s[a+dis]<s[c+dis];
// 由于是 LCP，那么 LCP+1 位肯定不同，就可以用这一位比较大小
}
bool ok(ll x) {
int cnt=1,Last=n;
fep(i,n,1) {
if(s[i]>s[L]) return 0;
if(!Cmp(i,Last,L,R)) ++cnt,Last=i;
if(cnt>lim) return 0;
}
return 1;
}
int main() {
lim=read(9),scanf("%s",s+1); n=strlen(s+1);
Suffix(); LCP(); init();
ll l=1,r=0,mid;
rep(i,1,n) r+=n-sa[i]+1-h[i];
while(l<=r) {
mid=l+r>>1;
Get(mid);
if(ok(mid)) ansl=L,ansr=R,r=mid-1;
else l=mid+1;
}
rep(i,ansl,ansr) putchar(s[i]); puts("");
return 0;
}