A palindrome is a string that reads the same from left to right as it does from right to left.

Given a string, $\mbox{S}$, of $N$ lowercase English letters, we define a $\boldsymbol{\mbox{k}}$-length rotation as cutting the first $\boldsymbol{\mbox{k}}$ characters from the beginning of $\mbox{S}$ and appending them to the end of $\mbox{S}$. For each $\mbox{S}$, there are $N$ possible $\boldsymbol{\mbox{k}}$-length rotations (where $0\leq k<N$). See the Explanation section for examples.

Given $N$ and $\mbox{S}$, find all $N$ $\boldsymbol{\mbox{k}}$-length rotations of $\mbox{S}$; for each rotated string, $S_{k}$, print the maximum possible length of any palindromic substring of $S_{k}$ on a new line.

Input Format

The first line contains an integer, $N$ (the length of $\mbox{S}$).

The second line contains a single string, $\mbox{S}$.

Constraints

$1\leq N\leq5\times10^5$
$0\leq k<N$
$\textit{$S is complicated of lower case English letters.}

Output Format

There should be $N$ lines of output, where each line $\boldsymbol{\mbox{k}}$ contains an integer denoting the maximum length of any palindromic substring of rotation $S_{k}$.

Sample Input 0

13
aaaaabbbbaaaa

Sample Output 0

12
12
10
8
8
9
11
13
11
9
8
8
10

Sample Input 1

7
cacbbba

Sample Output 1

3
3
3
3
3
3
3

Sample Input 2

12
eededdeedede

Sample Output 2

5
7
7
7
7
9
9
9
9
7
5
4

Explanation

Consider Sample Case 1, where $S=\text{"cacbbba"}$.

The possible rotations, $S_{k}$, for string $\mbox{S}$ are:

$S_0=\text{"cacbbba"}$.

$S_1=\text{"acbbac"}$

$S_2=\text{"cbbbea"}$

$S_3=\text{"bbacacac"}$

$S_4=\text{"bbacacab"}$

$S_5=\text{"bacacab"}$

$S_6=\text{"acacabb"}$

The longest palindromic substrings for each $S_{k}$ are:

$S_0:\text{"cac"}$ and $\text{"bbb}$, so we print their length ($3$) on a new line.

$S_1:\text{"bbb"}$, so we print its length ($3$) on a new line.

$S_2:\text{"bbb"}$ and $\text{"aca"}$, so we print their length ($3$) on a new line.

$S_3:\text{"bbb"},\text{"aca"}$ and $\text{"cac''}$, so we print their length ($3$) on a new line.

$S_4:\text{"aca''}$ and $\text{"cac''}$, so we print their length ($3$) on a new line.

$S_5:\text{"aca''}$ and $\text{"cac''}$, so we print their length ($3$) on a new line.

$S_6:\text{"aca"},\text{"cac"},$ and $\text{"bbb}$, so we print their length ($3$) on a new line.

见题面

见题面