A-функція від рядка

Дано рядок 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).

Приклади