CF961F.k-substrings

You 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.

给你一个由 $ n $ 个小写拉丁字母组成的字符串 $ s $。

我们定义 $ s $ 的第 $ k $ 个子串为字符串 $ \text{subs}k = s_k s{k+1} \dots s_{n+1-k} $。显然，$ \text{subs}_1 = s $，且这样的子串恰好有 个。

我们称某个字符串 $ t $ 是字符串 $ T $ 的一个奇真超前缀（odd proper suprefix），当且仅当满足以下条件：

• $ |T| > |t| $；
• $ |t| $ 是奇数；
• $ t $ 同时是 $ T $ 的前缀和后缀。

对于 $ s $ 的每一个 $ k $-子串（即 ），你需要计算其奇真超前缀的最大长度。

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.

第一行包含一个整数 $n$（$2 \leq n \leq 10^6$）——字符串 $s$ 的长度。

第二行包含一个由 $n$ 个小写拉丁字母组成的字符串 $s$。

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).

输出 个整数。其中第 $i$ 个整数应等于字符串 $s$ 的第 $i$ 个子串的所有奇数真“suprefix”（超前缀）的最大长度（若该子串不存在任何奇数真“suprefix”，则输出 $-1$）。

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

第一个样例测试的答案如下：

• 1-子串：bcabcabcabcabca
• 2-子串：cabcabcabcabc
• 3-子串：abcabcabcab
• 4-子串：bcabcabca
• 5-子串：cabcabc
• 6-子串：abcab
• 7-子串：bca
• 8-子串：c