#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
const int N=1e6+10;
char ai[N];
int sa[N],rk[N],het[N];//sa[i]代表排名为i的后缀是谁，rk[i]代表第i个后缀的排名是多少，het[i]表示排名为i的后缀和排名为i-1的后缀最长前缀是多少
int x[N],y[N],c[N];//x第一关键字，y第二关键字，c第一关键字的前缀和
int n,m;
void get_sa()
{
    for(int i=1;i<=n;i++)x[i]=ai[i];
    for(int i=1;i<=n;i++)c[x[i]]++;
    for(int i=2;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;
    for(int k=1;k<=n;k*=2)
    {
        int num=0;
        for(int i=n-k+1;i<=n;i++)y[++num]=i;
        for(int i=1;i<=n;i++)
        {
            if(sa[i]>k)
            {
                y[++num]=sa[i]-k;
            }
        }
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)c[x[i]]++;
        for(int i=2;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)
        {
            sa[c[x[y[i]]]--]=y[i];
            y[i]=0;
        }
        swap(x,y);
        x[sa[1]]=1,num=1;
        for(int i=2;i<=n;i++)
        {
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
            else x[sa[i]]=++num;
        }
        if(num==n)break;
        m=num;
    }
}
void get_het()
{
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;i++)
    {
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&ai[i+k]==ai[j+k])k++;
        het[rk[i]]=k;
    }
}
int main()
{
    scanf("%s",ai+1);
    n=strlen(ai+1),m=122;
    get_sa();
    for(int i=1;i<=n;i++) printf("%d ",sa[i]);
    printf("\n");
    get_het();
    for(int i=1;i<=n;i++) printf("%d ",het[i]);
    printf("\n");
    return 0;
}