F. k-substringstime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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  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.InputThe 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.OutputPrint  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).ExamplesInput15bcabcabcabcabcaOutput9 7 5 3 1 -1 -1 -1Input24abaaabaaaabaaabaaaabaaabOutput15 13 11 9 7 5 3 1 1 -1 -1 1Input19cabcabbcabcabbcabcaOutput5 3 1 -1 -1 1 1 -1 -1 -1NoteThe 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 
Input15bcabcabcabcabca
Output9 7 5 3 1 -1 -1 -1
['binary search', 'hashing', 'string suffix structures', '*2700']