#include <bits/stdc++.h>
using namespace std;
template <class T>
struct rge {
  T b, e;
};
template <class T>
rge<T> range(T i, T j) {
  return rge<T>{i, j};
}
struct debug {
  template <class T>
  debug& operator<<(const T&) {
    return *this;
  }
};
using ll = long long;
template <typename T>
void min_self(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void max_self(T& a, T b) {
  a = max(a, b);
}
const int mod = 1e9 + 7;
const int pr = 31;
const int mxN = 1000 * 1000 + 5;
int p31[mxN], pinv[mxN], ans[mxN], pre[mxN];
int add(int a, int b) {
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
  return a;
}
void add_self(int& a, int b) { a = add(a, b); }
int mul(int a, int b) { return 1LL * a * b % mod; }
int mpow(int a, int n) {
  if (n == 0) {
    return 1;
  }
  int x = mpow(a, n / 2);
  x = mul(x, x);
  if (n % 2 == 1) {
    x = mul(x, a);
  }
  return x;
}
int dont_use_hash(int i, int j) { return mul(pinv[i], add(pre[++j], -pre[i])); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  memset(ans, -1, sizeof ans);
  int n;
  cin >> n;
  p31[0] = pinv[0] = 1;
  for (int i = 1; i < n; i++) {
    p31[i] = mul(pr, p31[i - 1]);
    pinv[i] = mpow(p31[i], mod - 2);
  }
  string s;
  cin >> s;
  for (int i = 0; i < int(n); i++) {
    pre[i + 1] = add(pre[i], mul(s[i] - 'a' + 1, p31[i]));
  }
  for (int i = 0; i < n; i++) {
    int j = n - i - 1;
    if (i < j) {
      int lo = 0, hi = i;
      int best = -1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (dont_use_hash(i - mid, i + mid) ==
            dont_use_hash(j - mid, j + mid)) {
          best = mid;
          lo = mid + 1;
        } else {
          hi = mid - 1;
        }
      }
      if (best != -1) {
        max_self(ans[i - best], 2 * best + 1);
      }
    }
  }
  for (int i = 1; i < n; i++) {
    max_self(ans[i], ans[i - 1] - 2);
  }
  for (int i = 0; i < (n + 1) / 2; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}

### Prompt

Generate 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;
template <class T>
struct rge {
  T b, e;
};
template <class T>
rge<T> range(T i, T j) {
  return rge<T>{i, j};
}
struct debug {
  template <class T>
  debug& operator<<(const T&) {
    return *this;
  }
};
using ll = long long;
template <typename T>
void min_self(T& a, T b) {
  a = min(a, b);
}
template <typename T>
void max_self(T& a, T b) {
  a = max(a, b);
}
const int mod = 1e9 + 7;
const int pr = 31;
const int mxN = 1000 * 1000 + 5;
int p31[mxN], pinv[mxN], ans[mxN], pre[mxN];
int add(int a, int b) {
  a += b;
  while (a >= mod) a -= mod;
  while (a < 0) a += mod;
  return a;
}
void add_self(int& a, int b) { a = add(a, b); }
int mul(int a, int b) { return 1LL * a * b % mod; }
int mpow(int a, int n) {
  if (n == 0) {
    return 1;
  }
  int x = mpow(a, n / 2);
  x = mul(x, x);
  if (n % 2 == 1) {
    x = mul(x, a);
  }
  return x;
}
int dont_use_hash(int i, int j) { return mul(pinv[i], add(pre[++j], -pre[i])); }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  memset(ans, -1, sizeof ans);
  int n;
  cin >> n;
  p31[0] = pinv[0] = 1;
  for (int i = 1; i < n; i++) {
    p31[i] = mul(pr, p31[i - 1]);
    pinv[i] = mpow(p31[i], mod - 2);
  }
  string s;
  cin >> s;
  for (int i = 0; i < int(n); i++) {
    pre[i + 1] = add(pre[i], mul(s[i] - 'a' + 1, p31[i]));
  }
  for (int i = 0; i < n; i++) {
    int j = n - i - 1;
    if (i < j) {
      int lo = 0, hi = i;
      int best = -1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (dont_use_hash(i - mid, i + mid) ==
            dont_use_hash(j - mid, j + mid)) {
          best = mid;
          lo = mid + 1;
        } else {
          hi = mid - 1;
        }
      }
      if (best != -1) {
        max_self(ans[i - best], 2 * best + 1);
      }
    }
  }
  for (int i = 1; i < n; i++) {
    max_self(ans[i], ans[i - 1] - 2);
  }
  for (int i = 0; i < (n + 1) / 2; i++) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}

```