/*
  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;
}