#include #include #include #define LL long long #define Re register int using namespace std; const int N=4e5+10; int n,x,y,T;LL P,M,G,K;char s[N>>1]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } struct Sakura2{ int O,last,pos[N],siz[N],link[N],maxlen[N],trans[N][26]; // siz[x]: 节点x的出现次数 (endpos的大小) inline void insert(Re ch,Re id){ Re z=++O,p=last;pos[z]=id,siz[z]=1,maxlen[z]=maxlen[last]+1; while(p&&!trans[p][ch])trans[p][ch]=z,p=link[p]; if(!p)link[z]=1; else{ Re x=trans[p][ch]; if(maxlen[p]+1==maxlen[x])link[z]=x; else{ Re y=++O;maxlen[y]=maxlen[p]+1,pos[y]=pos[x]; for(Re i=0;i<26;++i)trans[y][i]=trans[x][i]; while(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p]; link[y]=link[x],link[z]=link[x]=y; } } last=z; } int t,ID[N],to[N][26];LL S[N]; inline void dfs1(Re x){ for(Re i=0;i<26;++i) if(to[x][i])dfs1(to[x][i]),siz[x]+=siz[to[x][i]]; } inline void dfs2(Re x){ if(x!=1)ID[++t]=x; for(Re i=0;i<26;++i)if(to[x][i])dfs2(to[x][i]); } inline LL calc(Re L,Re R){return 1ll*(L+R)*(R-L+1)/2;} inline void build(){ last=O=1; for(Re i=1;i<=n/2;++i)swap(s[i],s[n-i+1]); for(Re i=1;i<=n;++i)insert(s[i]-'a',i); for(Re i=2;i<=O;++i)to[link[i]][s[pos[i]-maxlen[link[i]]]-'a']=i; dfs1(1),dfs2(1); for(Re i=1;i<=t;++i)x=ID[i],S[i]=S[i-1]+1ll*siz[x]*calc(maxlen[link[x]]+1,maxlen[x]); } inline char ask(LL K){ Re l=1,r=t,x; while(l>1; if(S[mid]>1; if(1ll*siz[x]*calc(maxlen[link[x]]+1,mid)