A-funksiya bir sətirdən

Verilmiş S sətri, n simvoldan ibarətdir. Bu sətrin ilk i simvolları üçün A(i) funksiyasını aşağıdakı kimi təyin edək: A(i) elə mümkün olan maksimum k-yə bərabərdir ki, aşağıdakı sətirlər bərabər olsun:

S[1] + S[2] + S[3] + ... + S[k],

S[i] + S[i-1] + S[i-2] + ... + S[i-k+1],

burada S[i] - S sətrinin i-ci simvoludur və + işarəsi simvolların bir-birinin ardınca birləşdirildiyini göstərir.

Verilmiş sətir üçün bütün mümkün i dəyərləri üçün A funksiyasının dəyərini hesablayan proqram yazın.

Giriş məlumatları

Birinci sətirdə bir ədəd n (1 ≤ n ≤ 200000) verilir. İkinci sətirdə yalnız böyük və (və ya) kiçik latın hərflərindən ibarət uzunluğu n olan bir sətir verilir.

Çıxış məlumatları

A(1), A(2), ..., A(n) funksiyasının dəyərlərini göstərən n ədəd çıxarın.

Nümunələr