Дана строка s, состоящая из n строчных латинских букв.
Назовем k-подстрокой строки s строку subsk = sksk + 1..sn + 1 - k. очевидно, что subs1 = s и существует ровно 
таких подстрок.
Назовём нечётным собственным супрефиксом строки T такую строку t, что выполняются следующие условия:
- |T| > |t|;
- |t| нечётно;
- t является одновременно и префиксом, и суффиксом T.
Для каждой k-подстроки (
) s найдите наибольшую длину нечётного собственного супрефикса этой строки.
Выходные данные
Выведите целых чисел, где i-е число равно наибольшей длине нечётного собственного супрефикса i-подстроки s (или - 1, если у i-подстроки нет нечётных собственных супрефиксов).
Примечание
Ответ на первый пример следующий:
- 1-подстрока: bcabcabcabcabca
- 2-подстрока: cabcabcabcabc
- 3-подстрока: abcabcabcab
- 4-подстрока: bcabcabca
- 5-подстрока: cabcabc
- 6-подстрока: abcab
- 7-подстрока: bca
- 8-подстрока: c
Примеры
| № | Входные данные | Выходные данные |
|
1
|
15
bcabcabcabcabca
|
9 7 5 3 1 -1 -1 -1
|
|
2
|
24
abaaabaaaabaaabaaaabaaab
|
15 13 11 9 7 5 3 1 1 -1 -1 1
|
|
3
|
19
cabcabbcabcabbcabca
|
5 3 1 -1 -1 1 1 -1 -1 -1
|