给定一个由 n 个小写拉丁字母组成的字符串 s。
让我们将 s 的 k 子串表示为字符串 subsk = sksk + 1..sn + 1 - k。显然,subs1 = s,正好有$$\left\lceil \frac{n}{2} \right\rceil$$这样的子串。
让我们将某个字符串 t 称为字符串 T 的奇数真前缀,当且仅当满足以下条件:
- |T| > |t|;
- |t|是奇数;
- t 同时是 T 的前缀和后缀。
对于 s 的每个 k 子串 ($$k \in [1,\left\lceil \frac{n}{2} \right\rceil]$$) ,您必须计算其奇数真上前缀的最大长度。
输入
第一行包含一个整数 n (2 ≤ n ≤ 106) — 长度 s。
第二行包含由n个小写拉丁字母组成的字符串s。
输出
打印 $$\left\lceil \frac{n}{2} \right\rceil$$ 整数。其中第 i 个应该等于 s 的 i 子串的奇数真上前缀的最大长度(或者 - 1,如果不存在这样的字符串是 i 子串的奇数真上前缀)。
示例
输入 #1
15 bcabcabcabcabca
输出 #1
9 7 5 3 1 -1 -1 -1
输入 #2
24 abaaabaaaabaaabaaaabaaab
输出 #2
15 13 11 9 7 5 3 1 1 -1 -1 1
输入 #3
19 cabcabbcabcabbcabca
输出 #3
5 3 1 -1 -1 1 1 -1 -1 -1
注意
第一个样本测试的答案如下:
- 1-子字符串:bcabcabcabcabca
- 2-子串:cabcabcabcabc
- 3 个子字符串:abcabcabcab
- 4 个子串:bcabcabca
- 5-子串:cabcabc
- 6 个子串:abcab
- 7 个子串:bca
- 8 个子串:c