https://www.luogu.com.cn/record/197144497

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
int fath[maxn<<1],len[maxn<<1],tot,last,son[maxn<<1][26];
long long siz[maxn<<1],dp[maxn<<1];
char str[maxn];
vector<int>edge[maxn<<1];
inline void newnode(int siz){
	fath[++tot]=-1;
	len[tot]=siz;
	memset(son[tot],0,sizeof son[tot]);
}
inline void init(){
	tot=-1,last=0; newnode(0);
}
inline void ins(int ch){
	newnode(len[last]+1);
	int pre=last,now=tot; dp[now]=1;
	while(pre!=-1 and !son[pre][ch]){
		son[pre][ch]=now,pre=fath[pre];
	}
	last=tot;
	if(pre==-1) fath[now]=0;
	else{
		int tmp=son[pre][ch];
		if(len[tmp]==len[pre]+1) fath[now]=tmp;
		else{
			newnode(len[pre]+1);
			int temp=tot;
			for(int i=0;i<26;i++){
				son[temp][i]=son[tmp][i];
			}
			fath[temp]=fath[tmp];
			fath[now]=fath[tmp]=temp;
			while(pre!=-1 and son[pre][ch]==tmp){
				son[pre][ch]=temp,pre=fath[pre];
			}
		}
	}
}
inline void dfs(int u){
	if(siz[u]) return;
	if(u>0) siz[u]=1;
	for(int i=0;i<26;i++){
		if(son[u][i]){
			dfs(son[u][i]);
			siz[u]+=siz[son[u][i]];
		}
	}
}
inline void solve(int u,int k){
	if(siz[u]<k){cout<<"-1\n";return;}
	if(u>0) --k;
	if(k==0) return;
	for(int i=0;i<26;i++){
		if(son[u][i]){
			if(siz[son[u][i]]>=k){
				cout<<char('a'+i);
				if(k>1) solve(son[u][i],k);
				return;
			}
			else k-=siz[son[u][i]];
		}
	}
}
inline void dfs2(int u){
	for(int v:edge[u]){
		dfs2(v),dp[u]+=dp[v];
	}
	if(u==0) dp[u]=0;
	siz[u]=dp[u];
	for(int i=0;i<26;i++){
		if(son[u][i]) siz[u]+=siz[son[u][i]];
	}
}
inline void solve2(int u,int k){
	if(dp[u]>=k) return;
	k-=dp[u];
	for(int i=0;i<26;i++){
		if(son[u][i]){
			if(siz[son[u][i]]>=k){
				cout<<char('a'+i);
				solve2(son[u][i],k);
				return;
			}
			else k-=siz[son[u][i]];
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>str;
	int n=strlen(str);
	init();
	for(int i=0;i<n;i++) ins(str[i]-'a');
	int opt,k;cin>>opt>>k;
	if(opt==0) dfs(0),solve(0,k),cout<<"\n";
	else{
		if(k>1ll*(n)*(n+1)/2){
			cout<<"-1\n"; return 0;
		}
		for(int i=1;i<=tot;i++){
			edge[fath[i]].push_back(i);
		}
		dfs2(0),solve2(0,k);
	}
	return 0;
}