/// sa&lcp by muoii

#include <bits/stdc++.h>
using namespace std;
#define tag "spoj"
#define maxn 0
#define module 0
#define oo 1000000007LL
///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

int n;
string s;
vector<int> sa,rak,tmp,lcp;
int gap;

bool sufcmp(const int &x,const int &y){

    if (rak[x]!=rak[y]) return rak[x]<rak[y];
    return (x+gap<=n && y+gap<=n) ? rak[x+gap]<rak[y+gap] : x>y;
}

void buildSA(){
    sa=rak=tmp=vector<int>(n+1);

    for(int i=1;i<=n;i++) sa[i]=i,rak[i]=s[i],tmp[i]=0;

    for(gap=1;gap<=n && (gap==1 || rak[sa[n]]<n);gap<<=1)
    {
        sort(sa.begin()+1,sa.begin()+n+1,sufcmp);

        for(int i=1;i<=n;i++) tmp[sa[i]] = tmp[sa[i-1]] + sufcmp(sa[i-1],sa[i]);
        for(int i=1;i<=n;i++) rak[i]=tmp[i];
    }

}

void buildLCP(){
    lcp=vector<int>(n+1);

    for(int i=1,k=0;i<=n;i++)
        if(rak[i]>1)
        {
            for(int j=sa[rak[i]-1];s[i+k]==s[j+k];) ++k;

            lcp[rak[i]]=k;

            k-=(k>0);
        }
}

int main()
{
    #ifdef dmdd
    freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
    #endif // dmdd
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>s;n=s.size();s="$"+s;

    buildSA();buildLCP();
    for(int i=1;i<=n;i++) cout<<sa[i]<<" : "<<lcp[i]<<"\n";
    return 0;
}