#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 5;
int N, Len[MAX], ans[MAX];
char second[MAX];
set<int> S;
class Hash {
 public:
  int h, seed, mod;
  Hash(int _m = 0, int _s = 0) : mod(_m), seed(_s) {}
  void update(int x) { h = (1LL * h * seed + x) % mod; }
};
class PrefHash {
 public:
  Hash a;
  int ptr, mod, base[MAX], hash[MAX];
  PrefHash() {}
  void init(int _seed, int _mod, int _sz) {
    ptr = 0;
    mod = _mod;
    base[0] = 1;
    for (int i = 1; i <= (_sz); i++) base[i] = 1LL * base[i - 1] * _seed % mod;
    a.seed = _seed, a.mod = _mod, a.h = 0;
  }
  void update(int x) {
    a.update(x);
    hash[++ptr] = a.h;
  }
  int query(int l, int r) {
    return (hash[r] - 1LL * hash[l - 1] * base[r - l + 1] % mod + mod) % mod;
  }
} H;
bool same(int l1, int r1, int l2, int r2) {
  if (l1 <= 0 || r1 > N || l2 <= 0 || r2 > N) return 0;
  return H.query(l1, r1) == H.query(l2, r2);
}
int main() {
  scanf("%d", &N);
  scanf("%s", second + 1);
  H.init(623, 1e9 + 7, N);
  for (int i = 1; i <= (N); i++) H.update(second[i] - 'a' + 1);
  for (int i = 1; i <= ((N) / 2); i++) {
    int lft = i, rgt = N - i + 1;
    int l = -1, r = N + 1;
    while (l + 1 < r) {
      int m = l + r >> 1;
      if (same(lft - m, lft + m, rgt - m, rgt + m))
        l = m;
      else
        r = m;
    }
    Len[i] = l;
    S.insert(i);
  }
  memset(ans, -1, sizeof(ans));
  for (int i = (N) / 2; i > 0; i--)
    if (second[i] == second[N - i + 1]) {
      int lft = i - Len[i], rgt = i;
      set<int>::iterator it;
      while (1) {
        it = S.lower_bound(lft);
        if (it == S.end() || *it > rgt) break;
        ans[*it] = (i - *it) * 2 + 1;
        S.erase(it);
      }
    }
  for (int i = 1; i <= ((N + 1) / 2); i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 int MAX = 1e6 + 5;
int N, Len[MAX], ans[MAX];
char second[MAX];
set<int> S;
class Hash {
 public:
  int h, seed, mod;
  Hash(int _m = 0, int _s = 0) : mod(_m), seed(_s) {}
  void update(int x) { h = (1LL * h * seed + x) % mod; }
};
class PrefHash {
 public:
  Hash a;
  int ptr, mod, base[MAX], hash[MAX];
  PrefHash() {}
  void init(int _seed, int _mod, int _sz) {
    ptr = 0;
    mod = _mod;
    base[0] = 1;
    for (int i = 1; i <= (_sz); i++) base[i] = 1LL * base[i - 1] * _seed % mod;
    a.seed = _seed, a.mod = _mod, a.h = 0;
  }
  void update(int x) {
    a.update(x);
    hash[++ptr] = a.h;
  }
  int query(int l, int r) {
    return (hash[r] - 1LL * hash[l - 1] * base[r - l + 1] % mod + mod) % mod;
  }
} H;
bool same(int l1, int r1, int l2, int r2) {
  if (l1 <= 0 || r1 > N || l2 <= 0 || r2 > N) return 0;
  return H.query(l1, r1) == H.query(l2, r2);
}
int main() {
  scanf("%d", &N);
  scanf("%s", second + 1);
  H.init(623, 1e9 + 7, N);
  for (int i = 1; i <= (N); i++) H.update(second[i] - 'a' + 1);
  for (int i = 1; i <= ((N) / 2); i++) {
    int lft = i, rgt = N - i + 1;
    int l = -1, r = N + 1;
    while (l + 1 < r) {
      int m = l + r >> 1;
      if (same(lft - m, lft + m, rgt - m, rgt + m))
        l = m;
      else
        r = m;
    }
    Len[i] = l;
    S.insert(i);
  }
  memset(ans, -1, sizeof(ans));
  for (int i = (N) / 2; i > 0; i--)
    if (second[i] == second[N - i + 1]) {
      int lft = i - Len[i], rgt = i;
      set<int>::iterator it;
      while (1) {
        it = S.lower_bound(lft);
        if (it == S.end() || *it > rgt) break;
        ans[*it] = (i - *it) * 2 + 1;
        S.erase(it);
      }
    }
  for (int i = 1; i <= ((N + 1) / 2); i++) printf("%d ", ans[i]);
  puts("");
  return 0;
}

```