#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#define MAXN 500000
#define SIGMA 26
using namespace std;
struct node {
    int to[SIGMA];
    int maxl;
    int link;
};
int num=1,last=0;
node sa[2*MAXN-1];
int cnt[2*MAXN-1];
int add_node (int maxl) {
    sa[num].maxl=maxl;
    return num++;
}
int add_node (int maxl, node tmp) {
    sa[num]=move(tmp);
    return add_node(maxl);
}
void add_letter (int c) {
    int curr=last;
    last=add_node(sa[last].maxl+1);
    cnt[last]=1;
    while ((curr!=-1)&&(sa[curr].to[c]==0)) {
        sa[curr].to[c]=last;
        curr=sa[curr].link;
    }
    if (curr==-1) {
        sa[last].link=0;
        return ;
    }
    int nxt=sa[curr].to[c];
    if (sa[curr].maxl+1==sa[nxt].maxl) sa[last].link=nxt;
    else {
        int clone=add_node(sa[curr].maxl+1,sa[nxt]);
        sa[nxt].link=clone;
        sa[last].link=clone;
        while ((curr!=-1)&&(sa[curr].to[c]==nxt)) {
            sa[curr].to[c]=clone;
            curr=sa[curr].link;
        }
    }
}
void add_letter (char c) {
    add_letter(c-'a');
}

bool used[2*MAXN-1];
int maxr[2*MAXN-1];
vector <pair <int, int>> segs[MAXN+1];
void dfs (int vr) {
    if (used[vr]==true) return ;
    used[vr]=true;
    maxr[vr]=sa[vr].maxl;
    for (int i=0; i<SIGMA; i++) {
        int nxt=sa[vr].to[i];
        if (nxt==0) continue;
        dfs(nxt);
        if (cnt[nxt]==cnt[vr]) maxr[vr]=max(maxr[vr],maxr[nxt]);
    }
    //cout << vr << " " << sa[vr].maxl << " " << maxk[vr] << " " << cnt[vr] << endl ;
    segs[sa[vr].maxl].push_back({maxr[vr], cnt[vr]});
}

vector <pair <int, int>> tree[4*MAXN];
void build (int ind, int l, int r) {
    if (l==r) {
        tree[ind]=segs[l];
        sort(tree[ind].begin(),tree[ind].end());
        return ;
    }
    int mid=(l+r)/2;
    build(2*ind+1,l,mid);
    build(2*ind+2,mid+1,r);
    tree[ind].resize(tree[2*ind+1].size()+tree[2*ind+2].size());
    merge(tree[2*ind+1].begin(),tree[2*ind+1].end(),tree[2*ind+2].begin(),tree[2*ind+2].end(),tree[ind].begin());
}
void precalc (int ind, int l, int r) {
    for (int i=1; i<(int)tree[ind].size(); i++) {
        tree[ind][i].second=max(tree[ind][i].second,tree[ind][i-1].second);
    }
    if (l==r) return ;
    int mid=(l+r)/2;
    precalc(2*ind+1,l,mid);
    precalc(2*ind+2,mid+1,r);
}

int n;
vector <int> sorted[MAXN+1];
void start (char s[]) {
    n=strlen(s);
    sa[0].maxl=0;
    sa[0].link=-1;
    for (int i=0; i<n; i++) {
        add_letter(s[i]);
    }
    for (int i=0; i<num; i++) {
        sorted[sa[i].maxl].push_back(i);
    }
    for (int len=n; len>=1; len--) {
        for (auto ind : sorted[len]) {
            cnt[sa[ind].link]+=cnt[ind];
        }
    }
    dfs(0);
    build(0,1,n);
    precalc(0,1,n);
}

int query (int ind, int l, int r, int st, int fin) {
    if (st<=l) {
        int le=-1,ri=tree[ind].size();
        for (;;) {
            if (le==ri-1) break;
            int mid=(le+ri)/2;
            if (tree[ind][mid].first<=fin) le=mid;
            else ri=mid;
        }
        if (le==-1) return 0;
        return tree[ind][le].second;
    }
    int mid=(l+r)/2,ans=0;
    if (st<=mid) ans=query(2*ind+1,l,mid,st,fin);
    ans=max(ans,query(2*ind+2,mid+1,r,st,fin));
    return ans;
}
int round (int m, int k) {
    return query(0,1,n,m,k);
}
