Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. k-substrings

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a string *s* consisting of *n* lowercase Latin letters.

Let's denote *k*-substring of *s* as a string *subs*_{k} = *s*_{k}*s*_{k + 1}..*s*_{n + 1 - k}. Obviously, *subs*_{1} = *s*, and there are exactly 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 () of *s* you have to calculate the maximum length of its odd proper suprefix.

Input

The first line contains one integer *n* (2 ≤ *n* ≤ 10^{6}) — the length *s*.

The second line contains the string *s* consisting of *n* lowercase Latin letters.

Output

Print 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2018 06:59:28 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|