eolymp
bolt
Try our new interface for solving problems
Problems

A-function from a string

A-function from a string

Time limit 1 second
Memory limit 128 MiB

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 data

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

Output data

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

Examples

Input example #1
5
aabaa
Output example #1
1 2 0 1 5