#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 3e5 + 5;
const ULL bash = 131;
char str[N]; int n, s[N];
ULL d[N], f[N];
ULL get(int l, int r) { if (r > n) r = n; return f[r] - f[l - 1] * d[r - l + 1]; }
int solve(int x, int y)//求s[x,x+1……] 和 s[y,y+1……]的最长公共前缀长度
{
    int l = 0, r = n, res;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (get(x, x + mid - 1) == get(y, y + mid - 1)) l = mid + 1, res = mid;
        else r = mid - 1;
    }
    return res;
}
bool cmp(int x, int y)
{
    int len = solve(x, y);
    return str[x + len] < str[y + len];
}
int main()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    d[0] = 1; f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        d[i] = d[i - 1] * bash;
        f[i] = f[i - 1] * bash + str[i];
        s[i] = i;
    }
    sort(s + 1, s + n + 1, cmp);
    for (int i = 1; i <= n; i++) printf("%d ", s[i] - 1);
    puts("");
    for (int i = 1; i <= n; i++)
        if (i == 1) printf("0 ");
        else printf("%d ", solve(s[i - 1], s[i]));
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=3e5+5;
const ULL bash=131;
char str[N];int n,s[N];
ULL d[N],f[N];
ULL get(int l,int r){if(r>n)r=n;return f[r]-f[l-1]*d[r-l+1];}
int solve(int x,int y)//求s[x,x+1……] 和 s[y,y+1……]的最长公共前缀长度
{
    int l=0,r=n,res;
    while(l<=r)
	{
        int mid=(l+r)>>1;
        if(get(x,x+mid-1)==get(y,y+mid-1))l=mid+1,res=mid;
        else r=mid-1;
    }
    return res;
}
bool cmp(int x,int y)
{
    int len=solve(x,y);
    return str[x+len]<str[y+len];
}
int main()
{
    scanf("%s",str+1);
    n=strlen(str+1);
    d[0]=1;f[0]=0;
    for(int i=1;i<=n;i++)
	{
        d[i]=d[i-1]*bash;
        f[i]=f[i-1]*bash+str[i];
        s[i]=i;
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)printf("%d ",s[i]-1);
    puts("");
    for(int i=1;i<=n;i++)
        if(i==1)printf("0 ");
        else printf("%d ",solve(s[i-1],s[i]));
    return 0;
}