A-function from a string

A-function from a string

The string S of n characters is given. Lets define the function A(i) that depends on the first i characters of this line as follows: A(i) equals to the maximum possible value of k such that the next two strings are equal:

S[1] + S[2] + S[3] + … + S[k],

S[i] + S[i1] + S[i2] + … + S[ik+1],

where S[i] is the i-th character of S, and the sigh + means the concatination function.

Write a program that will find the values of a function A for a given string for all possible values of i from 1 to n.


The first line contains one number n (1 n200000). The second line contains a string of n uppercase and (or) lowercase latin characters.


Print n numbers - the values of function A(1), A(2), … A(n).

Time limit 1 second
Memory limit 64 MiB
Input example
Output example
1 2 0 1 5