#include<cstdio>

 #include<cstring>

 #define MAXN 1000005

 char str[MAXN];

 int n,str2[MAXN<<],p[MAXN<<];

 int main(){

     scanf("%s",str+); n=strlen(str+);

     memset(str2,-,sizeof str2);

     for(int i=;i<=n;++i)

         str2[i<<]=str[i];

     n=n<<|;

     int mpi=; p[]=; p[]=;

     for(int i=,j;i<=n;++i){

         j=(mpi<<)-i;

         if(j-p[j]<=mpi-p[mpi]){

             p[i]=mpi+p[mpi]-i;

             while(<i-p[i]&&i+p[i]<=n&&str2[i-p[i]]==str2[i+p[i]]) ++p[i];

             mpi=i;

         }

         else p[i]=p[j];

     }

     for(int i=;i<=n;++i) printf("%d ",str2[i]); puts("");

     for(int i=;i<=n;++i) printf("%d ",p[i]); puts("");

     return ;

 }