#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 100;
const int HASH_NUM = 10;
int AC[HASH_NUM] = {131, 137, 139, 149, 151, 157, 163, 167, 173, 179};
int ACC[HASH_NUM] = {200003, 200009, 200017, 200023, 200029,
                     200033, 200041, 200063, 200087, 200117};
long long bas[maxn][HASH_NUM];
int n;
char s[maxn];
long long sum1[maxn][HASH_NUM];
int ans[maxn];
bool check(int index, int x, int len) {
  long long hs1 = ((sum1[x + len - 1][index] -
                    sum1[x - 1][index] * bas[len][index] % ACC[index]) %
                       ACC[index] +
                   ACC[index]) %
                  ACC[index];
  long long hs2 = ((sum1[n - x + 1][index] - sum1[n - x - len + 1][index] *
                                                 bas[len][index] % ACC[index]) %
                       ACC[index] +
                   ACC[index]) %
                  ACC[index];
  if (hs1 == hs2)
    return true;
  else
    return false;
}
bool check(int x, int len) {
  for (int i = 0; i < HASH_NUM; i++) {
    if (!check(i, x, len)) return false;
  }
  return true;
}
int calc(int x) {
  for (int len = n - 2 * (x - 1) - 1; len; len--) {
    if (len % 2 && check(x, len)) {
      return len;
    }
  }
  return -1;
}
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int o = 0; o < HASH_NUM; o++) {
    bas[0][o] = 1;
    for (int i = 1; i <= n; i++) {
      bas[i][o] = bas[i - 1][o] * AC[o] % ACC[o];
    }
    for (int i = 1; i <= n; i++) {
      sum1[i][o] = (sum1[i - 1][o] * AC[o] % ACC[o] + s[i] - 'a' + 1) % ACC[o];
    }
  }
  int topi = (n + 1) >> 1;
  for (int i = topi; i >= 1; i--) {
    if (i == topi) {
      if (n % 2 == 1) {
        ans[i] = -1;
      } else {
        if (s[i] == s[i + 1]) {
          ans[i] = 1;
        } else {
          ans[i] = -1;
        }
      }
    } else {
      ans[i] = ans[i + 1] + 2;
      while (ans[i] != -1 && check(i, ans[i]) == false) {
        ans[i] -= 2;
      }
    }
  }
  for (int i = 1; i <= topi; i++) {
    printf("%d ", ans[i]);
  }
  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 int maxn = 1e6 + 100;
const int HASH_NUM = 10;
int AC[HASH_NUM] = {131, 137, 139, 149, 151, 157, 163, 167, 173, 179};
int ACC[HASH_NUM] = {200003, 200009, 200017, 200023, 200029,
                     200033, 200041, 200063, 200087, 200117};
long long bas[maxn][HASH_NUM];
int n;
char s[maxn];
long long sum1[maxn][HASH_NUM];
int ans[maxn];
bool check(int index, int x, int len) {
  long long hs1 = ((sum1[x + len - 1][index] -
                    sum1[x - 1][index] * bas[len][index] % ACC[index]) %
                       ACC[index] +
                   ACC[index]) %
                  ACC[index];
  long long hs2 = ((sum1[n - x + 1][index] - sum1[n - x - len + 1][index] *
                                                 bas[len][index] % ACC[index]) %
                       ACC[index] +
                   ACC[index]) %
                  ACC[index];
  if (hs1 == hs2)
    return true;
  else
    return false;
}
bool check(int x, int len) {
  for (int i = 0; i < HASH_NUM; i++) {
    if (!check(i, x, len)) return false;
  }
  return true;
}
int calc(int x) {
  for (int len = n - 2 * (x - 1) - 1; len; len--) {
    if (len % 2 && check(x, len)) {
      return len;
    }
  }
  return -1;
}
int main() {
  scanf("%d", &n);
  scanf("%s", s + 1);
  for (int o = 0; o < HASH_NUM; o++) {
    bas[0][o] = 1;
    for (int i = 1; i <= n; i++) {
      bas[i][o] = bas[i - 1][o] * AC[o] % ACC[o];
    }
    for (int i = 1; i <= n; i++) {
      sum1[i][o] = (sum1[i - 1][o] * AC[o] % ACC[o] + s[i] - 'a' + 1) % ACC[o];
    }
  }
  int topi = (n + 1) >> 1;
  for (int i = topi; i >= 1; i--) {
    if (i == topi) {
      if (n % 2 == 1) {
        ans[i] = -1;
      } else {
        if (s[i] == s[i + 1]) {
          ans[i] = 1;
        } else {
          ans[i] = -1;
        }
      }
    } else {
      ans[i] = ans[i + 1] + 2;
      while (ans[i] != -1 && check(i, ans[i]) == false) {
        ans[i] -= 2;
      }
    }
  }
  for (int i = 1; i <= topi; i++) {
    printf("%d ", ans[i]);
  }
  return 0;
}

```