#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e16 + 61;
long double inv = 1. / (long double)mod;
long long mul(long long a, long long b) {
  long long x = (long long)((long double)a * (long double)b * inv +
                            (long double)(1) / 2.);
  long long ret = a * b - mod * x;
  if ((long long)(ret) < 0) ret += mod;
  return ret;
}
long long add(long long a, long long b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
long long sub(long long a, long long b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
const int N = 1e6 + 10;
const long long base = 97;
long long H[N];
char s[N];
long long pw[N];
int F[N];
inline long long getHash(int i, int j) {
  return sub(H[j], mul(H[i - 1], pw[j - i + 1]));
}
int main() {
  int n;
  pw[0] = 1;
  for (int i = 1; i < N; i++) pw[i] = mul(pw[i - 1], base);
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) {
    H[i] = add(mul(H[i - 1], base), s[i] - 'a' + 1);
  }
  int l, r;
  if (n & 1) {
    l = r = (1 + n) >> 1;
    F[l] = -1;
  } else {
    l = n >> 1;
    r = l + 1;
    F[l] = (s[l] == s[r]) ? 1 : -1;
  }
  while (1) {
    l--;
    r++;
    if (l <= 0) break;
    F[l] = -1;
    if (s[l] == s[r]) F[l] = 1;
    for (int k = min(r - l, F[l + 1] + 2); k >= 1; k -= 2) {
      if (getHash(l, l + k - 1) == getHash(r - k + 1, r)) {
        F[l] = k;
        break;
      }
    }
  }
  for (int k = 1; k <= n + 1 - k; k++) printf("%d ", F[k]);
}

### Prompt

Your challenge is to write a Cpp solution to 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 mod = 1e16 + 61;
long double inv = 1. / (long double)mod;
long long mul(long long a, long long b) {
  long long x = (long long)((long double)a * (long double)b * inv +
                            (long double)(1) / 2.);
  long long ret = a * b - mod * x;
  if ((long long)(ret) < 0) ret += mod;
  return ret;
}
long long add(long long a, long long b) {
  a += b;
  if (a >= mod) a -= mod;
  return a;
}
long long sub(long long a, long long b) {
  a -= b;
  if (a < 0) a += mod;
  return a;
}
const int N = 1e6 + 10;
const long long base = 97;
long long H[N];
char s[N];
long long pw[N];
int F[N];
inline long long getHash(int i, int j) {
  return sub(H[j], mul(H[i - 1], pw[j - i + 1]));
}
int main() {
  int n;
  pw[0] = 1;
  for (int i = 1; i < N; i++) pw[i] = mul(pw[i - 1], base);
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int i = 1; i <= n; i++) {
    H[i] = add(mul(H[i - 1], base), s[i] - 'a' + 1);
  }
  int l, r;
  if (n & 1) {
    l = r = (1 + n) >> 1;
    F[l] = -1;
  } else {
    l = n >> 1;
    r = l + 1;
    F[l] = (s[l] == s[r]) ? 1 : -1;
  }
  while (1) {
    l--;
    r++;
    if (l <= 0) break;
    F[l] = -1;
    if (s[l] == s[r]) F[l] = 1;
    for (int k = min(r - l, F[l + 1] + 2); k >= 1; k -= 2) {
      if (getHash(l, l + k - 1) == getHash(r - k + 1, r)) {
        F[l] = k;
        break;
      }
    }
  }
  for (int k = 1; k <= n + 1 - k; k++) printf("%d ", F[k]);
}

```