//Algorytm Manachera
//www.algorytm.org
//Emil Hotkowski

#include <cstdlib>
#include <iostream>
#define N 10 //Dlugosc rozpatrywanego slowa

using namespace std;

//Funkcja pomocnicza - zwraca maksimum z dwoch liczb
inline int max(int a ,int b)
{
    if(a >b)return a;
    else return b;
}

//Funkcja pomocnicza - zwraca minimum z dwoch liczb
inline int min(int a ,int b)
{
    if(a <b)return a;
    else return b;
}       

//Program
int main(int argc, char *argv[])
{
    char s[N+2]; //utworz tablice przechowywujaca slowo
    int R[N+2];  //utworz tablice przechowywujaca rozwiazania
    s[0]='#';    //specjalny znacznik poczatku slowa (nie moze wystepowac w slowie)
    s[N]='$';    //specjalny znacznik konca slowa (nie moze wystepowac w slowie)
    for(int i = 1; i <= N; i++) cin >> s[i];//pobierz N znakow
    
    //Oblicz promienie palindromow parzystych
    int i = 1;
    int t = 0;
    R[0] = 0;
    while(i <= N)
    {
        while(s[i-t] == s[i + t+1])t++; //oblicz wielkosc palindromu parzystego o srodku w punkcie i
        R[i] = t;

        //Algorytm Manachera
        int k = 1;
        while(k <= t && R[i - k] != R[i] - k)
        {
            R[i + k] = min(R[i-k],(R[i]-k));
            k++;
        }
        t-=k;
        t=max(0,t);
        i+=k;
    }       
    
    //Wypisz wyniki
    for(int i = 1; i <= N; i++) cout << s[i] << " ";
    cout << "\n" << " ";
    for(int i = 1; i < N; i++) cout << R[i] << " ";     
    
    system("PAUSE");
    return EXIT_SUCCESS;
}