Дано рядок S, який складається з n символів. Визначимо функцію A(i) від перших i символів цього рядка наступним чином: A(i) дорівнює такому максимально можливому k, що наступні рядки рівні:

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

S[i] + S[i–1] + S[i–2] + … + S[i–k+1],

   де S[i] – i-ий символ рядка S, а знак + означає, що символи записуються у рядок безпосередньо один за одним.

   Напишіть програму, яка обчислить значення функції A для заданого рядка для всіх можливих значень i від 1 до n.

   Вхідні дані

   У першому рядку записано одне число n (1 ≤ n ≤ 200000). У другому рядку записано рядок довжиною n символів, що складається лише з великих і (або) маленьких латинських літер.

   Вихідні дані

   Виведіть n чисел - значення функції A(1), A(2), … A(n).