#include <bits/stdc++.h>
using namespace std;
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
char S[1000004];
long long Hash[1000004][2];
long long base[2] = {37, 47}, Mod[2] = {1000000007, 1000000009};
long long power[1000004][2];
vector<int> ans;
int main() {
  int n = getnum();
  scanf("%s", S + 1);
  for (int b = 0; b <= 1; b++) {
    power[0][b] = 1;
    for (int i = 1; i <= n; i++) {
      power[i][b] = (power[i - 1][b] * base[b]) % Mod[b];
      Hash[i][b] = (Hash[i - 1][b] * base[b] + S[i] - 'a' + 1) % Mod[b];
    }
  }
  int l, r, cur;
  if (n % 2)
    l = r = n / 2 + 1, cur = -1;
  else
    r = (l = n / 2) + 1, cur = 1;
  for (; l >= 1; l--, r++) {
    while (cur > 0) {
      int yes = 1;
      for (int b = 0; b <= 1; b++) {
        long long x =
            (((Hash[l + cur - 1][b] - Hash[l - 1][b] * power[cur][b]) %
              Mod[b]) +
             Mod[b]) %
            Mod[b];
        long long y =
            (((Hash[r][b] - Hash[r - cur][b] * power[cur][b]) % Mod[b]) +
             Mod[b]) %
            Mod[b];
        if (x != y) yes = 0;
      }
      if (yes) break;
      cur -= 2;
    }
    ans.push_back(cur);
    cur += 2;
  }
  while (ans.size()) {
    printf("%d ", ans.back());
    ans.pop_back();
  }
}

### 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;
inline long long getnum() {
  char c = getchar();
  long long num, sign = 1;
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (num = 0; c >= '0' && c <= '9';) {
    c -= '0';
    num = num * 10 + c;
    c = getchar();
  }
  return num * sign;
}
char S[1000004];
long long Hash[1000004][2];
long long base[2] = {37, 47}, Mod[2] = {1000000007, 1000000009};
long long power[1000004][2];
vector<int> ans;
int main() {
  int n = getnum();
  scanf("%s", S + 1);
  for (int b = 0; b <= 1; b++) {
    power[0][b] = 1;
    for (int i = 1; i <= n; i++) {
      power[i][b] = (power[i - 1][b] * base[b]) % Mod[b];
      Hash[i][b] = (Hash[i - 1][b] * base[b] + S[i] - 'a' + 1) % Mod[b];
    }
  }
  int l, r, cur;
  if (n % 2)
    l = r = n / 2 + 1, cur = -1;
  else
    r = (l = n / 2) + 1, cur = 1;
  for (; l >= 1; l--, r++) {
    while (cur > 0) {
      int yes = 1;
      for (int b = 0; b <= 1; b++) {
        long long x =
            (((Hash[l + cur - 1][b] - Hash[l - 1][b] * power[cur][b]) %
              Mod[b]) +
             Mod[b]) %
            Mod[b];
        long long y =
            (((Hash[r][b] - Hash[r - cur][b] * power[cur][b]) % Mod[b]) +
             Mod[b]) %
            Mod[b];
        if (x != y) yes = 0;
      }
      if (yes) break;
      cur -= 2;
    }
    ans.push_back(cur);
    cur += 2;
  }
  while (ans.size()) {
    printf("%d ", ans.back());
    ans.pop_back();
  }
}

```