/*
Copyright 2013 Marek "p2004a" Rusinowski
Manacher algorithm
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN 1000000
using namespace std;
char str[ MAXN] ;
int R[ MAXN] ;
void manacher( char * str, int len, int * R, bool odd) {
fill( R, R + len, 0 ) ;
for ( int k, i = odd; i < len; i + = k) {
while ( i + R[ i] < len && i - R[ i] - odd >= 0 && str[ i + R[ i] ] == str[ i - R[ i] - odd] ) ++ R[ i] ;
for ( k = 1 ; k < R[ i] && R[ i] - k ! = R[ i - k] ; ++ k) R[ i + k] = min( R[ i] - k, R[ i - k] ) ;
R[ i + k] = max( min( R[ i] - k, R[ i - k] ) , 0 ) ;
}
}
int main( ) {
int n;
scanf ( "%d%s" , & n, str) ;
for ( int j = 0 ; j < 2 ; ++ j) {
manacher( str, n, R, j) ;
for ( int i = 0 ; i < n; ++ i) {
printf ( j ? " %c" : "%c " , str[ i] ) ;
}
printf ( "\n " ) ;
for ( int i = 0 ; i < n; ++ i) {
printf ( "%d " , R[ i] ) ;
}
printf ( "\n " ) ;
}
return 0 ;
}
LyoKICBDb3B5cmlnaHQgMjAxMyBNYXJlayAicDIwMDRhIiBSdXNpbm93c2tpCiAgTWFuYWNoZXIgYWxnb3JpdGhtCiovCiNpbmNsdWRlIDxjc3RkaW8+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KCiNkZWZpbmUgTUFYTiAxMDAwMDAwCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2hhciBzdHJbTUFYTl07CmludCBSW01BWE5dOwoKdm9pZCBtYW5hY2hlcihjaGFyICpzdHIsIGludCBsZW4sIGludCAqUiwgYm9vbCBvZGQpIHsKICBmaWxsKFIsIFIgKyBsZW4sIDApOwogIGZvciAoaW50IGssIGkgPSBvZGQ7IGkgPCBsZW47IGkgKz0gaykgewogICAgd2hpbGUgKGkgKyBSW2ldIDwgbGVuICYmIGkgLSBSW2ldIC0gb2RkID49IDAgJiYgc3RyW2kgKyBSW2ldXSA9PSBzdHJbaSAtIFJbaV0gLSBvZGRdKSArK1JbaV07CiAgICBmb3IgKGsgPSAxOyBrIDwgUltpXSAmJiBSW2ldIC0gayAhPSBSW2kgLSBrXTsgKytrKSBSW2kgKyBrXSA9IG1pbihSW2ldIC0gaywgUltpIC0ga10pOwogICAgUltpICsga10gPSBtYXgobWluKFJbaV0gLSBrLCBSW2kgLSBrXSksIDApOwogIH0KfQoKaW50IG1haW4oKSB7CiAgaW50IG47CiAgc2NhbmYoIiVkJXMiLCAmbiwgc3RyKTsKICBmb3IgKGludCBqID0gMDsgaiA8IDI7ICsraikgewogICAgbWFuYWNoZXIoc3RyLCBuLCBSLCBqKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgIHByaW50ZihqID8gIiAlYyIgOiAiJWMgIiwgc3RyW2ldKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgIHByaW50ZigiJWQgIiwgUltpXSk7CiAgICB9CiAgICBwcmludGYoIlxuIik7CiAgfQogIHJldHVybiAwOwp9Cg==