#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 3;
const double eps = 1e-6;
const double pi = acos(-1.0);
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const int maxn = 1e6 + 6;
long long ha1[maxn], ha2[maxn];
long long p1[maxn], p2[maxn];
long long get1(int l, int r) {
  return (ha1[r] - ha1[l - 1] * p1[r - l + 1] % mod1 + mod1) % mod1;
}
long long get2(int l, int r) {
  return (ha2[r] - ha2[l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
}
bool check(int l1, int r1, int l2, int r2) {
  long long a1 = get1(l1, r1);
  long long b1 = get1(l2, r2);
  long long a2 = get2(l1, r1);
  long long b2 = get2(l2, r2);
  bool ok = true;
  ok &= a1 == b1;
  ok &= a2 == b2;
  return ok;
}
int n;
const int q = 13331;
char s[maxn];
void init() {
  p1[0] = p2[0] = 1;
  for (int i = (1); i <= (n); i++) {
    p1[i] = (p1[i - 1] * q) % mod1;
    p2[i] = (p2[i - 1] * q) % mod2;
    ha1[i] = (ha1[i - 1] * q % mod1 + s[i]) % mod1;
    ha2[i] = (ha2[i - 1] * q % mod2 + s[i]) % mod2;
  }
}
int ans[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  cin >> (s + 1);
  init();
  for (int i = (1); i <= (n >> 1); i++) {
    int l = 1, r = i;
    int x = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (check(i - (mid - 1), i + mid - 1, n - i + 1 - (mid - 1),
                n - i + 1 + mid - 1))
        x = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    ans[i - x + 1] = x * 2 - 1;
  }
  for (int i = (1); i <= (n + 1 >> 1); i++) {
    ans[i] = max(ans[i], ans[i - 1] - 2);
    if (ans[i] == 0) ans[i] = -1;
    print(ans[i], (i == n + 1 >> 1) ? '\n' : ' ');
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

You are given a string s consisting of n lowercase Latin letters.

Let's denote k-substring of s as a string subsk = sksk + 1..sn + 1 - k. Obviously, subs1 = s, and there are exactly <image> such substrings.

Let's call some string t an odd proper suprefix of a string T iff the following conditions are met:

  * |T| > |t|; 
  * |t| is an odd number; 
  * t is simultaneously a prefix and a suffix of T.



For evey k-substring (<image>) of s you have to calculate the maximum length of its odd proper suprefix.

Input

The first line contains one integer n (2 ≤ n ≤ 106) — the length s.

The second line contains the string s consisting of n lowercase Latin letters.

Output

Print <image> integers. i-th of them should be equal to maximum length of an odd proper suprefix of i-substring of s (or  - 1, if there is no such string that is an odd proper suprefix of i-substring).

Examples

Input

15
bcabcabcabcabca


Output

9 7 5 3 1 -1 -1 -1


Input

24
abaaabaaaabaaabaaaabaaab


Output

15 13 11 9 7 5 3 1 1 -1 -1 1


Input

19
cabcabbcabcabbcabca


Output

5 3 1 -1 -1 1 1 -1 -1 -1

Note

The answer for first sample test is folowing: 

  * 1-substring: bcabcabcabcabca
  * 2-substring: cabcabcabcabc
  * 3-substring: abcabcabcab
  * 4-substring: bcabcabca
  * 5-substring: cabcabc
  * 6-substring: abcab 
  * 7-substring: bca 
  * 8-substring: c 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 3;
const double eps = 1e-6;
const double pi = acos(-1.0);
template <typename T1, typename T2>
void ckmin(T1 &a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
void ckmax(T1 &a, T2 b) {
  if (a < b) a = b;
}
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template <typename T>
void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void print(T x, char let) {
  print(x), putchar(let);
}
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
const int maxn = 1e6 + 6;
long long ha1[maxn], ha2[maxn];
long long p1[maxn], p2[maxn];
long long get1(int l, int r) {
  return (ha1[r] - ha1[l - 1] * p1[r - l + 1] % mod1 + mod1) % mod1;
}
long long get2(int l, int r) {
  return (ha2[r] - ha2[l - 1] * p2[r - l + 1] % mod2 + mod2) % mod2;
}
bool check(int l1, int r1, int l2, int r2) {
  long long a1 = get1(l1, r1);
  long long b1 = get1(l2, r2);
  long long a2 = get2(l1, r1);
  long long b2 = get2(l2, r2);
  bool ok = true;
  ok &= a1 == b1;
  ok &= a2 == b2;
  return ok;
}
int n;
const int q = 13331;
char s[maxn];
void init() {
  p1[0] = p2[0] = 1;
  for (int i = (1); i <= (n); i++) {
    p1[i] = (p1[i - 1] * q) % mod1;
    p2[i] = (p2[i - 1] * q) % mod2;
    ha1[i] = (ha1[i - 1] * q % mod1 + s[i]) % mod1;
    ha2[i] = (ha2[i - 1] * q % mod2 + s[i]) % mod2;
  }
}
int ans[maxn];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  cin >> (s + 1);
  init();
  for (int i = (1); i <= (n >> 1); i++) {
    int l = 1, r = i;
    int x = 0;
    while (l <= r) {
      int mid = l + r >> 1;
      if (check(i - (mid - 1), i + mid - 1, n - i + 1 - (mid - 1),
                n - i + 1 + mid - 1))
        x = mid, l = mid + 1;
      else
        r = mid - 1;
    }
    ans[i - x + 1] = x * 2 - 1;
  }
  for (int i = (1); i <= (n + 1 >> 1); i++) {
    ans[i] = max(ans[i], ans[i - 1] - 2);
    if (ans[i] == 0) ans[i] = -1;
    print(ans[i], (i == n + 1 >> 1) ? '\n' : ' ');
  }
  return 0;
}

```