#include <bits/stdc++.h>
using namespace std;
const int C = 1000001, L = 22;
int sget(char tab[]) {
  for (int z = 0;; z++) {
    tab[z] = getchar();
    if (tab[z] <= 32) return z;
  }
}
int pom[C], pom2[C], pom3[C], tw[C];
void countsort(int t1[], int t2[], int t3[], int n) {
  int i, lst = 0, c, mx = 0;
  for (i = 0; i <= n; i++) {
    tw[t1[i]]++;
    if (t1[i] > mx) mx = t1[i];
  }
  for (i = 0; i <= mx; i++)
    if (tw[i] > 0) c = tw[i], tw[i] = lst, lst += c;
  for (i = 0; i <= n; i++) {
    c = tw[t1[i]];
    pom[c] = t1[i], pom2[c] = t2[i], pom3[c] = t3[i];
    tw[t1[i]]++;
  }
  for (i = 0; i <= n; i++)
    tw[i] = 0, t1[i] = pom[i], t2[i] = pom2[i], t3[i] = pom3[i];
  for (i = n; i <= mx; i++) tw[i] = 0;
}
int tk[L][C], pw[L], pos[C], pa[C], pb[C];
int lcp(int a, int b, int j) {
  int wn = 0;
  while (j >= 0) {
    if (tk[j][a] != tk[j][b])
      j--;
    else
      wn += pw[j], a += pw[j], b += pw[j];
  }
  return wn;
}
void suf_arr(char k[], int n, int sa[], int lcpv[]) {
  int i, j;
  for (i = 0; i < L; i++) pw[i] = 1 << i;
  for (i = 0; i < n; i++) tk[0][i] = k[i] - 96;
  for (j = 1; pw[j - 1] < n; j += 1) {
    for (i = 0; i < n; i++) {
      if (i + pw[j - 1] < n)
        pb[i] = tk[j - 1][i + pw[j - 1]];
      else
        pb[i] = 0;
      pa[i] = tk[j - 1][i];
      pos[i] = i;
    }
    countsort(pb, pa, pos, n - 1);
    countsort(pa, pb, pos, n - 1);
    tk[j][pos[0]] = 1;
    for (i = 1; i < n; i++) {
      if ((pa[i] > pa[i - 1]) || (pa[i] == pa[i - 1] && pb[i] > pb[i - 1]))
        tk[j][pos[i]] = tk[j][pos[i - 1]] + 1;
      else
        tk[j][pos[i]] = tk[j][pos[i - 1]];
    }
  }
  for (i = 0; i < n; i++) pa[i] = tk[j - 1][i], pos[i] = i;
  countsort(pa, pos, pb, n - 1);
  for (i = 0; i < n - 1; i++)
    sa[i] = pos[i], lcpv[i] = lcp(pos[i], pos[i + 1], j - 1);
  lcpv[n - 1] = 0, sa[n - 1] = pos[n - 1];
}
int rmq[L][C], lg2[C];
void rmq_init(int n, int st[]) {
  int i, j;
  for (i = 0; i < n; i++)
    rmq[0][i] = st[i], lg2[i] = ((i > 1) ? (lg2[i / 2] + 1) : 0);
  for (i = 0; i < L; i++) pw[i] = 1 << i;
  for (j = 1; j < L; j++) {
    for (i = 0; i < n; i++) {
      if (i + pw[j - 1] >= n)
        rmq[j][i] = rmq[j - 1][i];
      else
        rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + pw[j - 1]]);
    }
  }
}
int x;
int rmqq(int a, int b) {
  if (a > b) a = b + a, b = a - b, a = a - b;
  b--;
  x = lg2[b - a];
  return min(rmq[x][a], rmq[x][b - pw[x] + 1]);
}
char k[C], q;
int sa[C], lp[C], ps[C], wynn[C];
int main() {
  int n, beg, end, i, lim, j;
  scanf("%d", &n);
  q = getchar();
  sget(k);
  if (n % 2 == 0)
    beg = n / 2 - 1, end = n / 2, lim = n / 2;
  else
    beg = n / 2 - 1, end = n / 2 + 1, wynn[end] = -1, lim = n / 2 + 1;
  suf_arr(k, n, sa, lp);
  rmq_init(n, lp);
  for (i = 0; i < n; i++) ps[sa[i]] = i;
  for (; beg >= 0; beg--) {
    while (rmqq(ps[beg], ps[end]) < lim - end + 1 && end <= lim) end += 2;
    wynn[beg] = (lim - end + 1);
    if (wynn[beg] == 0) wynn[beg] = -1;
    end--, lim++;
  }
  for (i = 0; i < n / 2; i++) printf("%d ", wynn[i]);
  if (n % 2 == 1) printf("%d\n", -1);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 C = 1000001, L = 22;
int sget(char tab[]) {
  for (int z = 0;; z++) {
    tab[z] = getchar();
    if (tab[z] <= 32) return z;
  }
}
int pom[C], pom2[C], pom3[C], tw[C];
void countsort(int t1[], int t2[], int t3[], int n) {
  int i, lst = 0, c, mx = 0;
  for (i = 0; i <= n; i++) {
    tw[t1[i]]++;
    if (t1[i] > mx) mx = t1[i];
  }
  for (i = 0; i <= mx; i++)
    if (tw[i] > 0) c = tw[i], tw[i] = lst, lst += c;
  for (i = 0; i <= n; i++) {
    c = tw[t1[i]];
    pom[c] = t1[i], pom2[c] = t2[i], pom3[c] = t3[i];
    tw[t1[i]]++;
  }
  for (i = 0; i <= n; i++)
    tw[i] = 0, t1[i] = pom[i], t2[i] = pom2[i], t3[i] = pom3[i];
  for (i = n; i <= mx; i++) tw[i] = 0;
}
int tk[L][C], pw[L], pos[C], pa[C], pb[C];
int lcp(int a, int b, int j) {
  int wn = 0;
  while (j >= 0) {
    if (tk[j][a] != tk[j][b])
      j--;
    else
      wn += pw[j], a += pw[j], b += pw[j];
  }
  return wn;
}
void suf_arr(char k[], int n, int sa[], int lcpv[]) {
  int i, j;
  for (i = 0; i < L; i++) pw[i] = 1 << i;
  for (i = 0; i < n; i++) tk[0][i] = k[i] - 96;
  for (j = 1; pw[j - 1] < n; j += 1) {
    for (i = 0; i < n; i++) {
      if (i + pw[j - 1] < n)
        pb[i] = tk[j - 1][i + pw[j - 1]];
      else
        pb[i] = 0;
      pa[i] = tk[j - 1][i];
      pos[i] = i;
    }
    countsort(pb, pa, pos, n - 1);
    countsort(pa, pb, pos, n - 1);
    tk[j][pos[0]] = 1;
    for (i = 1; i < n; i++) {
      if ((pa[i] > pa[i - 1]) || (pa[i] == pa[i - 1] && pb[i] > pb[i - 1]))
        tk[j][pos[i]] = tk[j][pos[i - 1]] + 1;
      else
        tk[j][pos[i]] = tk[j][pos[i - 1]];
    }
  }
  for (i = 0; i < n; i++) pa[i] = tk[j - 1][i], pos[i] = i;
  countsort(pa, pos, pb, n - 1);
  for (i = 0; i < n - 1; i++)
    sa[i] = pos[i], lcpv[i] = lcp(pos[i], pos[i + 1], j - 1);
  lcpv[n - 1] = 0, sa[n - 1] = pos[n - 1];
}
int rmq[L][C], lg2[C];
void rmq_init(int n, int st[]) {
  int i, j;
  for (i = 0; i < n; i++)
    rmq[0][i] = st[i], lg2[i] = ((i > 1) ? (lg2[i / 2] + 1) : 0);
  for (i = 0; i < L; i++) pw[i] = 1 << i;
  for (j = 1; j < L; j++) {
    for (i = 0; i < n; i++) {
      if (i + pw[j - 1] >= n)
        rmq[j][i] = rmq[j - 1][i];
      else
        rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + pw[j - 1]]);
    }
  }
}
int x;
int rmqq(int a, int b) {
  if (a > b) a = b + a, b = a - b, a = a - b;
  b--;
  x = lg2[b - a];
  return min(rmq[x][a], rmq[x][b - pw[x] + 1]);
}
char k[C], q;
int sa[C], lp[C], ps[C], wynn[C];
int main() {
  int n, beg, end, i, lim, j;
  scanf("%d", &n);
  q = getchar();
  sget(k);
  if (n % 2 == 0)
    beg = n / 2 - 1, end = n / 2, lim = n / 2;
  else
    beg = n / 2 - 1, end = n / 2 + 1, wynn[end] = -1, lim = n / 2 + 1;
  suf_arr(k, n, sa, lp);
  rmq_init(n, lp);
  for (i = 0; i < n; i++) ps[sa[i]] = i;
  for (; beg >= 0; beg--) {
    while (rmqq(ps[beg], ps[end]) < lim - end + 1 && end <= lim) end += 2;
    wynn[beg] = (lim - end + 1);
    if (wynn[beg] == 0) wynn[beg] = -1;
    end--, lim++;
  }
  for (i = 0; i < n / 2; i++) printf("%d ", wynn[i]);
  if (n % 2 == 1) printf("%d\n", -1);
  return 0;
}

```