k-부분 문자열

n개의 소문자 라틴 문자로 이루어진 문자열 s가 주어진다.

s의 k-부분 문자열을 문자열 subsk = sksk + 1..sn + 1 - k로 나타내자s. 명백히 subs1 = s이며, 그러한 부분 문자열은 정확히 개 있다.

어떤 문자열 t가 다음 조건들을 만족할 때, 그리고 그럴 때에만 이를 문자열 T의 홀수 진부분 수프리픽스라고 부르자s.

• |T| > |t|;
• |t|는 홀수이다;
• t는 T의 접두사이면서 동시에 접미사이다.

s의 모든 k-부분 문자열 ()에 대해, 그 홀수 진부분 수프리픽스의 최대 길이를 계산해야 한다.

첫째 줄에는 정수 하나 n (2 ≤ n ≤ 106)가 주어진다. 이는 길이 s이다.

둘째 줄에는 n개의 소문자 라틴 문자로 이루어진 문자열 s가 주어진다.

개의 정수를 출력한다. 그중 i-th번째 정수는 s의 i-부분 문자열의 홀수 진부분 수프리픽스의 최대 길이와 같아야 한다(또는 i-부분 문자열의 홀수 진부분 수프리픽스인 문자열이 없다면 - 1).

첫 번째 예제 테스트의 답은 다음과 같다.

• 1-부분 문자열: bcabcabcabcabca
• 2-부분 문자열: cabcabcabcabc
• 3-부분 문자열: abcabcabcab
• 4-부분 문자열: bcabcabca
• 5-부분 문자열: cabcabc
• 6-부분 문자열: abcab
• 7-부분 문자열: bca
• 8-부분 문자열: c