# A-function from a string

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

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

Input #1

Answer #1

Submissions 937

Acceptance rate 38%