We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Circular Palindromes

Circular Palindromes

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

Given a string, , of lowercase English letters, we define a -length rotation as cutting the first characters from the beginning of and appending them to the end of . For each , there are possible -length rotations (where ). See the Explanation section for examples.

Given and , find all -length rotations of ; for each rotated string, , print the maximum possible length of any palindromic substring of on a new line.

Input Format

The first line contains an integer, (the length of ).
The second line contains a single string, .

Constraints

Output Format

There should be lines of output, where each line contains an integer denoting the maximum length of any palindromic substring of rotation .

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 .

The possible rotations, , for string are:
.





The longest palindromic substrings for each are:
and , so we print their length () on a new line.
, so we print its length () on a new line.
and , so we print their length () on a new line.
and , so we print their length () on a new line.
and , so we print their length () on a new line.
and , so we print their length () on a new line.
and , so we print their length () on a new line.