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[i–1] + S[i–2] + … + S[i–k+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.

   Input

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

   Output

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