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

where S[i] is the i-th character of S, and the sigh + means the concatenation 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).

Examples