#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+10;

inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}

int n;
char s[maxn];
int sa[maxn],rk[maxn<<1],cnt[maxn],oldsa[maxn],oldrk[maxn<<1];
int height[maxn];
bool cmp(int x,int y,int l){
    return oldrk[x]==oldrk[y]&&oldrk[x+l]==oldrk[y+l];
}
inline void get_sa(){
    int m=max(n,127);
    for(int i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
    for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
    for(int l=1;;l<<=1){
        int k=0;
        for(int i=n;i+l>n;--i) oldsa[++k]=i;
        for(int i=1;i<=n;++i) if(sa[i]>l) oldsa[++k]=sa[i]-l;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i) ++cnt[rk[oldsa[i]]];
        for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i) sa[cnt[rk[oldsa[i]]]--]=oldsa[i];
        for(int i=1;i<=n;++i) oldrk[i]=rk[i];
        k=0;
        for(int i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],l)?k:++k;
        m=k;
        if(k==n) break;
    }
    for(int i=1,k=0;i<=n;++i){
        if(k) --k;
        while(s[i+k]==s[sa[rk[i]-1]+k]) ++k;
        height[rk[i]]=k;
    }
}

int stmn[maxn][20];
inline void build(){
    for(int i=1;i<=n;++i) stmn[i][0]=height[i];
    for(int k=1;k<=19;++k){
        for(int i=1;i+(1<<k)-1<=n;++i){
            stmn[i][k]=min(stmn[i][k-1],stmn[i+(1<<k-1)][k-1]);
        }
    }
}
inline int query(int l,int r){
    l=rk[l],r=rk[r];
    if(l>r) swap(l,r);
    ++l;
    int k=__lg(r-l+1);
    return min(stmn[l][k],stmn[r-(1<<k)+1][k]);
}
int now,nxt;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    get_sa();
    // for(int i=1;i<=n;++i) cerr<<rk[i]<<" ";
    // cerr<<endl;
    build();
    now=1,nxt=0;
    for(int i=1;i<=n;++i){
        if(rk[i]>rk[now]){
            // cerr<<i+query(now,i)<<endl;
            if(!nxt||i+query(now,i)<=nxt+query(now,nxt)) nxt=i;
        }
        if(nxt&&nxt+query(now,nxt)==i){
            now=nxt,nxt=0;
        }
        // cerr<<"i:"<<i<<" now:"<<now<<" nxt:"<<nxt<<endl;
        printf("%d %d\n",now,i);
    }
    return 0;
}