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.
## 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 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).
[samples]
## Note
The answer for first sample test is folowing:
* 1-substring: bcabca**bca****bcabca**
* 2-substring: cabcab**c****abcabc**
* 3-substring: abcabc**abcab**
* 4-substring: bcabca**bca**
* 5-substring: cabcab**c**
* 6-substring: abcab
* 7-substring: bca
* 8-substring: c
你被给定一个由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。
记 #cf_span[k]-子串 为字符串 #cf_span[subsk = sksk + 1..sn + 1 - k]。显然，#cf_span[subs1 = s]，并且恰好存在这样的子串。
称某个字符串 #cf_span[t] 为字符串 #cf_span[T] 的 *奇数真前缀*，当且仅当满足以下条件：
对于 #cf_span[s] 的每一个 #cf_span[k]-子串，你需要计算其奇数真前缀的最大长度。
第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 106)] —— 字符串 #cf_span[s] 的长度。
第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。
请输出 #cf_span[n/2] 个整数。第 #cf_span[i] 个整数应等于 #cf_span[s] 的第 #cf_span[i]-子串的奇数真前缀的最大长度（如果不存在这样的奇数真前缀，则输出 #cf_span[ - 1]）。
## Input
第一行包含一个整数 #cf_span[n] #cf_span[(2 ≤ n ≤ 106)] —— 字符串 #cf_span[s] 的长度。第二行包含由 #cf_span[n] 个小写拉丁字母组成的字符串 #cf_span[s]。
## Output
请输出 #cf_span[n/2] 个整数。第 #cf_span[i] 个整数应等于 #cf_span[s] 的第 #cf_span[i]-子串的奇数真前缀的最大长度（如果不存在这样的奇数真前缀，则输出 #cf_span[ - 1]）。
[samples]
## Note
第一个样例的答案如下：
1-子串：#cf_span(class=[tex-font-style-underline], body=[bcabca*bca*])*bcabca*
2-子串：#cf_span(class=[tex-font-style-underline], body=[cabcab*c*])*abcabc*
3-子串：#cf_span(class=[tex-font-style-underline], body=[abcab])c*abcab*
4-子串：#cf_span(class=[tex-font-style-underline], body=[bca])bca*bca*
5-子串：#cf_span(class=[tex-font-style-underline], body=[c])abcab*c*
6-子串：abcab
7-子串：bca
8-子串：c
**Definitions**
Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 10^6 $.
Let $ s = s_1 s_2 \dots s_n $ be a string of length $ n $ over the alphabet of lowercase Latin letters.
For each $ k \in \{1, 2, \dots, \lfloor \frac{n+1}{2} \rfloor\} $, define the $ k $-substring:
$$
s^{(k)} = s_k s_{k+1} \dots s_{n+1-k}
$$
Note: $ s^{(1)} = s $, and $ s^{(k)} $ has length $ n - 2(k - 1) $.
A string $ t $ is an *odd proper suprefix* of a string $ T $ if:
- $ t $ is a prefix of $ T $,
- $ t $ is also a suffix of $ T $,
- $ t \neq T $ (proper),
- $ |t| $ is odd.
**Constraints**
1. $ 2 \leq n \leq 10^6 $
2. $ s_i \in \{a, b, \dots, z\} $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each $ k \in \{1, 2, \dots, \lfloor \frac{n+1}{2} \rfloor\} $, compute:
$$
L_k = \max \left\{ \ell \in \mathbb{Z}^+ \mid \ell \text{ is odd},\; \ell < |s^{(k)}|,\; s^{(k)}[1..\ell] = s^{(k)}[|s^{(k)}|-\ell+1..|s^{(k)}|] \right\}
$$
If no such $ \ell $ exists, set $ L_k = -1 $.
Output the sequence $ L_1, L_2, \dots, L_{\lfloor (n+1)/2 \rfloor} $.