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 $$\left\lceil \frac{n}{2} \right\rceil$$ 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 ($$k \in [1,\left\lceil \frac{n}{2} \right\rceil]$$) 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 $$\left\lceil \frac{n}{2} \right\rceil$$ 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).

见题面 Input 部分

见题面 Output 部分

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