#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
int n,pos[400004],nxt[400004][26],len[400004],fa[400004],lst=1,cnt=1;
char s[200004];
void ins(int c,int i){
int p=lst;int np=lst=++cnt;
len[np]=len[p]+1,pos[np]=i;
for(;p&&!nxt[p][c];p=fa[p])nxt[p][c]=np;
if(!p)fa[np]=1;
else{
int q=nxt[p][c];
if(len[q]==len[p]+1)fa[np]=q;
else{
int nq=++cnt;
memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));
fa[nq]=fa[q];
len[nq]=len[p]+1,fa[q]=fa[np]=nq;
for(;p&&nxt[p][c]==q;p=fa[p])nxt[p][c]=nq;
}
}
}
vectorg[400004],qry[200004];
int kmp[200004],rt[400004];
int tot,fi[4000004],ed[4000004],dif[4000004],son[2][4000004];
int merge(int i1,int i2){
if(!i1||!i2)return i1|i2;
son[0][i1]=merge(son[0][i1],son[0][i2]);
son[1][i1]=merge(son[1][i1],son[1][i2]);
dif[i1]=max(max(dif[son[0][i1]],dif[son[1][i1]]),fi[son[1][i1]]-ed[son[0][i1]]);
fi[i1]=son[0][i1]?fi[son[0][i1]]:fi[son[1][i1]];
ed[i1]=son[1][i1]?ed[son[1][i1]]:ed[son[0][i1]];
return i1;
}
int ins(int i,int l,int r,int p){
if(!i)i=++tot;
if(l==r)fi[i]=ed[i]=p,dif[i]=0;
else{
int md=(l+r)>>1;
if(p<=md)son[0][i]=ins(son[0][i],l,md,p);
else son[1][i]=ins(son[1][i],md+1,r,p);
dif[i]=max(max(dif[son[0][i]],dif[son[1][i]]),fi[son[1][i]]-ed[son[0][i]]);
fi[i]=son[0][i]?fi[son[0][i]]:fi[son[1][i]];
ed[i]=son[1][i]?ed[son[1][i]]:ed[son[0][i]];
}
return i;
}
void dfs(int x){
for(auto y:g[x])dfs(y),rt[x]=merge(rt[x],rt[y]);
if(pos[x])rt[x]=ins(rt[x],1,n,pos[x]);
if(x>1){
int L=len[fa[x]]+1,R=len[x];
int FI=fi[rt[x]],ED=ed[rt[x]],DIF=dif[rt[x]];
L=max(L,FI-kmp[FI]),L=max(L,DIF);
if(L<=R)qry[ED-L+1].push_back(ED),qry[ED-R].push_back(-ED);
}
}
int pmk[200004],bit[200004],ansl=0,ansr=1e9;
setST;
void upd(int i,int x){
for(;i;i-=i&-i)bit[i]+=x;
}
int ask(int i){
int ans=0;
for(;i<=n;i+=i&-i)ans+=bit[i];
return ans;
}
ll ans;
const int H1=257,M1=998244353,H2=31,M2=1e9+7;
int hs1[200004],hs2[200004],hp1[200004],hp2[200004];
pii hashqry(int l,int r){
l–;
int v1=(hs1[r]-(ll)hs1[l]*hp1[r-l]%M1+M1)%M1;
int v2=(hs2[r]-(ll)hs2[l]*hp2[r-l]%M2+M2)%M2;
return {v1,v2};
}
int main(){
scanf("%s",s+1),n=strlen(s+1);
hp1[0]=hp2[0]=1;
for(int i=1;i<=n;i++){
hp1[i]=(ll)hp1[i-1]*H1%M1,hs1[i]=((ll)hs1[i-1]*H1+s[i])%M1;
hp2[i]=(ll)hp2[i-1]*H2%M2,hs2[i]=((ll)hs2[i-1]*H2+s[i])%M2;
}
fi[0]=-1e9,ed[0]=1e9;
int now=0;
for(int i=1;i<=n;i++){
ins(s[i]-‘a’,i);
if(i>1){
while(now>0&&s[i]!=s[now+1])now=kmp[now];
if(s[i]==s[now+1])now++;kmp[i]=now;
}
}
for(int i=2;i<=cnt;i++)g[fa[i]].push_back(i);
dfs(1);
pmk[n]=n+1,now=n+1;
for(int i=n-1;i;i–){
while(now<=n&&s[i]!=s[now-1])now=pmk[now];
if(s[i]==s[now-1])now–;pmk[i]=now;
}
for(int i=n;i;i–){
if(!qry[i].empty()){
sort(qry[i].begin(),qry[i].end());
for(auto x:qry[i]){
if(x>0)ST.insert(x),upd(x,1);
else ST.erase(-x),upd(-x,-1);
}
}
int ret=ask(pmk[i]-1);
ans+=ret;
if(ret>0){
int R=(*ST.lower_bound(pmk[i]-1));
if(ansr-ansl>R-i)ansl=i,ansr=R;
else if(ansr-ansl==R-i){
int l=0,r=R-i+2;
while(r>l+1){
int md=(l+r)>>1;
if(hashqry(ansl,ansl+md-1)!=hashqry(i,i+md-1)||md>R-i+1)r=md;
else l=md;
}
if(s[ansl+r-1]>s[i+r-1])ansl=i,ansr=R;
}
}
}
printf("%lld\n",ans);
// if(ansl<1||ansr>n)return 0;
for(int i=ansl;i<=ansr;i++)putchar(s[i]);
}
