思路

考虑后缀数组。

$t=0$ 的比较 easy，这里不多考虑。

考虑 $t=1$ 的情况怎么做。

暴力建小根笛卡尔树。

如果当前层有答案，立刻得解，否则左右子树分别做。

解完。

Code

实际常数巨大，根本过不去。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
namespace SUF_ARRAY
{
    struct ST
    {
        typedef std::vector<uint>vec;
        vec Log2;std::vector<vec>Val;
        voi bzr(){Val.clear(),Log2.clear();}
        voi build(vec A)
        {
            uint n=A.size();bzr(),Val.push_back(A),Log2.resize(n+1);
            Log2[0]=-1u;for(uint i=1;i<=n;i++)Log2[i]=Log2[i>>1]+1;
            for(uint len=2,dep=1;len<=n;len<<=1,dep++)
            {
                Val.push_back(vec(n-len+1));for(uint i=0;i+len<=n;i++)Val[dep][i]=std::min(Val[dep-1][i],Val[dep-1][i+(len>>1)]);
            }
        }
        uint find(uint l,uint r){uint dep=Log2[r-l];return std::min(Val[dep][l],Val[dep][r-(1u<<dep)]);}
    };
    template<typename T>
    class SufArray
    {
        private:
            typedef std::vector<uint>vec;vec rk,sa,h;ST p;
        public:
            voi bzr(){rk.clear(),sa.clear(),h.clear(),p.bzr();}
            voi build(std::vector<T>User,bol op=true)
            {
                uint n=User.size();bzr();if(!n)return;
                rk.resize(n),sa.resize(n),h.resize(n);
                {
                    typedef std::pair<T,uint>Pair;
                    std::vector<Pair>q(n);
                    for(uint i=0;i<n;i++)q[i]=Pair(User[i],i);
                    std::sort(q.begin(),q.end());
                    rk[q[0].second]=0;for(uint i=1;i<n;i++)rk[q[i].second]=(q[i].first==q[i-1].first)?rk[q[i-1].second]:i;
                }
                {
                    typedef std::pair<uint,uint>Pair;
                    typedef std::pair<Pair,uint>Pair2;
                    std::vector<Pair2>q(n),tmp(n);
                    for(uint dep=1;dep<n;dep<<=1)
                    {
                        for(uint i=0;i<n;i++)q[i]=Pair2(Pair(rk[i],(i+dep<n)?rk[i+dep]+1:0),i);
                        {
                            vec cnt(n+1);
                            for(uint i=0;i<n;i++)cnt[q[i].first.second]++;
                            for(uint i=0;i<n;i++)cnt[i+1]+=cnt[i];
                            for(uint i=0;i<n;i++)tmp[--cnt[q[i].first.second]]=q[i];
                        }
                        {
                            vec cnt(n);
                            for(uint i=0;i<n;i++)cnt[tmp[i].first.first]++;
                            for(uint i=1;i<n;i++)cnt[i]+=cnt[i-1];
                            for(uint i=n-1;i+1;i--)q[--cnt[tmp[i].first.first]]=tmp[i];
                        }
                        rk[q[0].second]=0;for(uint i=1;i<n;i++)rk[q[i].second]=(q[i].first==q[i-1].first)?rk[q[i-1].second]:i;
                    }
                }
                for(uint i=0;i<n;i++)sa[rk[i]]=i;
                for(uint i=0,k=0;i<n;i++)
                {
                    if(k)k--;
                    if(rk[i])
                    {
                        for(uint j=sa[rk[i]-1];i+k<n&&j+k<n&&User[i+k]==User[j+k];k++);
                        h[rk[i]]=k;
                    }
                }
                if(op)lcp_ready();
            }
            voi build(T*User,uint n,bol op=true){
                std::vector<T>QAQ(n);for(uint i=0;i<n;i++)QAQ[i]=User[i];
                build(QAQ,op);
            }
            voi lcp_ready(){p.build(h);}
            uint size(){return sa.size();}
            uint rank(uint num){return rk[num];}
            uint SA(uint num){return sa[num];}
            uint height(uint num){return h[num];}
            uint lcp(uint a,uint b){return(a==b)?size()-a:(rk[a]<rk[b]?p.find(rk[a]+1,rk[b]+1):p.find(rk[b]+1,rk[a]+1));}
            uint lcp2(uint l,uint r){return(l+1==r)?size()-sa[l]:p.find(l+1,r);}
    };
}
using namespace SUF_ARRAY;
typedef SufArray<chr>SA;
chr C[500005];SA S;
uint n,k;
std::vector<uint>User[500005];
voi dfs(uint l,uint r,uint done)
{
    if(l>=r)return;
    uint v=S.lcp2(l,r);
    if(k<(ullt)(v-done)*(r-l))
    {
        k=k/(r-l)+done;
        for(uint i=0;i<=k;i++)putchar(C[i+S.SA(l)]);
        putchar('\n');
        exit(0);
    }
    k-=(ullt)(v-done)*(r-l);
    done=v;
    if(l+1<r)
    {
        uint w=*std::upper_bound(User[v].begin(),User[v].end(),l);
        dfs(l,w,done);
        dfs(w,r,done);
    }
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    uint t;scanf("%s%u",C,&t);for(n=0;C[n];n++);
    S.build(C,n,0);
    if(t==0)
    {
        scanf("%u",&k);k--;
        for(uint i=0;i<n;k-=n-S.SA(i)-S.height(i),i++)
            if(k<n-S.SA(i)-S.height(i))
            {
                for(uint j=S.SA(i);j<=S.height(i)+S.SA(i)+k;j++)
                    putchar(C[j]);
                putchar('\n');
                return 0;
            }
        puts("-1");
    }
    else{
        S.lcp_ready();
        scanf("%u",&k);
        for(uint i=0;i<n;i++)User[S.height(i)].push_back(i);
        if(--k>=(ullt)n*(n+1)/2)return puts("-1"),0;
        dfs(0,n,0);
    }
    return 0;
}