#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,M,cnt,rk[100001],tmp[100001],sa[100001],tag[100001],height[100001];
long long ans;
char s[100002];
void Sort()
{
for(register int i=1;i<=M;i++)tag[i]=0;
for(register int i=1;i<=n;i++)tag[rk[i]]++;
for(register int i=1;i<=M;i++)tag[i]+=tag[i-1];
for(register int i=n;i>=1;i--)sa[tag[rk[tmp[i]]]--]=tmp[i];
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
M=76;
for(register int i=1;i<=n;i++)
rk[i]=s[i]-'0',tmp[i]=i;
Sort();
for(register int len=1;cnt<n;len<<=1,M=cnt)
{
cnt=0;
for(register int i=n-len+1;i<=n;i++)tmp[++cnt]=i;
for(register int i=1;i<=n;i++)
if(sa[i]>len)
tmp[++cnt]=sa[i]-len;
Sort();
swap(rk,tmp);
rk[sa[1]]=cnt=1;
for(register int i=2;i<=n;i++)
rk[sa[i]]=tmp[sa[i]]==tmp[sa[i-1]]&&tmp[sa[i]+len]==tmp[sa[i-1]+len]?cnt:++cnt;
}
for(register int i=1,len=0;i<=n;i++)
{
if(len)len--;
int now=sa[rk[i]-1];
while(s[now+len]==s[i+len])len++;
height[rk[i]]=len;
}
for(register int i=1;i<=n;i++)
printf("%d ",sa[i]);
cout<<endl;
for(register int i=2;i<=n;i++)
printf("%d ",height[i]);
}