//lg p3809 sa模板题
//Copyright yeyou26

//额外数据测试lcp
//input:aabaaaab
//output:sa:4 5 6 1 7 2 8 3 
//      lcp:0 3 2 3 1 2 0 1 
#include<bits/stdc++.h>
using namespace std;

#define w where

const int N = (int)3e6;

int n,m=256;//后缀个数 桶个数(m初始值为值域(应该是吧))
int where[N];//第i个后缀在哪个桶里
int y[N];//临时数组
int c[N];//计数排序的计数数组
int sa[N];//排名为i的后缀
int rk[N];//第i个后缀的排名
int lcp[N];//排名为i的后缀跟排名为i-1的后缀的最长公共前缀的长度

char s[N];

void init();
void get_sa();
void get_lcp();

int main()
{
    freopen("working.in","r",stdin);
    freopen("working.out","w",stdout);
    init();
    get_sa();
    for(int i=1;i<=n;i++) printf("%d ",sa[i]);
    printf("\n");
    get_lcp();
    for(int i=1;i<=n;i++) printf("%d ",lcp[i]);
    return 0;
}

void init()
{
    cin>>(s+1);
    n=strlen(s+1);
}

//Function Implementation

void get_lcp()
{
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
    for(int i=1,k=0;i<=n;i++) //枚举第i个后缀
    {
        if(rk[i]==1) continue;//排名为1的后缀的lcp=0
        if(k) k--; //定理:lcp[rk[i]]>=lcp[rk[i-1]]-1;
        int j=sa[rk[i]-1]; //从排名上看，i后缀的前临后缀j
        while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;//暴力枚举
        lcp[rk[i]]=k;
    }
}

void get_sa()
{
    //第一次计数排序，按第一个字母排
    for(int i=1;i<=n;i++) c[w[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i>=1;i--) sa[c[w[i]]--]=i;
    for(int k=1;k<=n;k<<=1)
    {
        //按 后半段字符串 进行计数排序
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++) y[i]=sa[i];
        for(int i=1;i<=n;i++) c[w[y[i]+k]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[w[y[i]+k]]--]=y[i];
        //按 前半段字符串 进行计数排序
        memset(c,0,sizeof(c));
        for(int i=1;i<=n;i++) y[i]=sa[i];
        for(int i=1;i<=n;i++) c[w[y[i]]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[w[y[i]]]--]=y[i];
        //把排好序的 长度为2k的字符串 放到桶里 并 重新计算桶的个数
        m=0;
        for(int i=1;i<=n;i++) y[i]=w[i];
        for(int i=1;i<=n;i++)
        {
            if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) w[sa[i]]=m;
            else w[sa[i]]=++m;
        }
        if(m==n) break; //桶个数跟后缀一样多，说明已经排好了
    }
}