【题目描述】：
    很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。
    首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。
    现在他想找一个最优的分法让“魔力串”字典序最小。
【题目解法】：
    显然答案具有单调性，且答案一定是原串的一个子串
    因此我们二分K，验证第K小子串是否满足要求
    首先我么求出原串的后缀数组，然后可以在O(N)时间内找到K小子串，设为[L,R]
    然后我们贪心的从后往前一个一个字符加入，假设现在已经分段到j，那么我们i=j i--，知道找到某个子串[i,j]满足[L,R]<[i,j]，那么此时我们必须在i和i+1直接分开，因此此时我们把需要分开的次数+1，然后j=i，继续向前找，可以证明这样划分的方案是最优的
    我们只要判断最后需要划分的次数是否小于等于给出的k即可
    当然如果对于某个单个字符[i,i]满足[L,R]<[i,i]显然这个字符串是不满足的，因为我们无法把[i,i]分割开来
    时间复杂度O(N log N)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=200005;
int n,m,rank[N],sa[N],x[N],y[N],L,R,tot;
int height[N],f[21][N],c[N]; char s[N];
long long l,r,mid,ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    tot=getint(); l=1; r=0; ans=0;
    scanf("%s",s+1); n=strlen(s+1); m=200;
}
void suffix_array()
{
    for (int i=1; i<=n; i++) c[x[i]=s[i]]++;
    for (int i=1; i<=m; i++) c[i]+=c[i-1];
    for (int i=1; i<=n; i++) sa[c[x[i]]--]=i;
    for (int p=1;p<n;p=p*2)
    {
        int tot=0; for (int i=n-p+1; i<=n; i++) y[++tot]=i;
        for (int i=1; i<=n; i++) if (sa[i]>p) y[++tot]=sa[i]-p;
        for (int i=1; i<=m; i++) c[i]=0;
        for (int i=1; i<=n; i++) c[x[i]]++;
        for (int i=1; i<=m; i++) c[i]+=c[i-1];
        for (int i=n; i>=1; i--) sa[c[x[y[i]]]--]=y[i]; m=0;
        for (int i=1; i<=n; i++)
        {
            if (i==1) {y[sa[i]]=++m; continue;}
            int u=sa[i-1],v=sa[i];
            if ((x[u]!=x[v])||(x[u+p]!=x[v+p])) m++; y[v]=m;
        }
        if (m>=n) break;
        for (int i=1; i<=n; i++) x[i]=y[i];
    }
    for (int i=1; i<=n; i++) rank[sa[i]]=i;
}
void calc()
{
    for (int i=1,h=0; i<=n; i++)
    {
        if (rank[i]==1) continue; int j=sa[rank[i]-1];
        while ((i+h<=n)&&(j+h<=n)&&(s[i+h]==s[j+h])) h++;
        height[rank[i]]=h; if (h>0) h--;
    }
    for (int i=1; i<=n; i++) f[0][i]=height[i];
    for (int i=1; i<=20; i++)
        for (int j=1; j<=n; j++)
        {
            if (j+(1<<i)-1>n) continue; f[i][j]=f[i-1][j];
            f[i][j]=min(f[i][j],f[i-1][j+(1<<(i-1))]);
        }
    for (int i=1; i<=n; i++) r+=(long long)(n-sa[i]+1);
    for (int i=1; i<=n; i++) r-=(long long)height[i];
}
void Kth(long long k)
{
    long long now=0;
    for (int i=1; i<=n; i++)
    {
        int j=sa[i]; long long len=n-j+1-height[i];
        if (now+len<k) {now+=len; continue;}
        k-=now; L=j; R=j+height[i]+k-1; return;
    }
}
inline int ask(int x,int y)
{
    if (x>y) swap(x,y); x++; int len=y-x+1;
    int k=(int)(log(len)/log(2));
    return min(f[k][x],f[k][y-(1<<k)+1]);
}
inline int cmp(int x1,int y1,int x2,int y2)
{
    if (x1==x2)
    {
        if (y1>y2) return 1;
        if (y1==y2) return 0;
        if (y1<y2) return -1;
    }
    int len1=y1-x1+1,len2=y2-x2+1;
    int len=ask(rank[x1],rank[x2]);
    if ((len>=len1)&&(len>=len2)) return 0;
    if (len>=len1) return -1;
    if (len>=len2) return 1;
    if (s[x1+len]>s[x2+len]) return 1;
    return -1;
}
inline bool judge()
{
    int cnt=0;
    for (int i=n,j=n; (i>=1)&&(j>=1);)
    {
        if (cmp(L,R,i,j)!=-1) {i--; continue;}
        if (i==j) {cnt=tot+1; break;} j=i; cnt++;
        if (cnt>=tot) break;
    }
    return cnt<tot;
}
void solve()
{
    while (l<=r)
    {
        mid=(l+r)/2; Kth(mid); 
        if (judge()) ans=mid,r=mid-1; else l=mid+1;
    }
    Kth(ans);
    for (int i=L; i<=R; i++) printf("%c",s[i]); printf("\n");
}
int main()
{
    init();
    suffix_array();
    calc();
    solve();
    return 0;
}