Заданий непустий рядок, довжина якого не перевищує \(10^6\). Необхідно для кожної позиції символа в рядку знайти довжину найбільшого паліндрома з центром в цьому символі. Рядок складається з літер англійської абетки. Малі і великі літери вважаються різними

Формат вхідних даних

Рядок, довжиною не більше \(10^6\)

Формат вихідних даних

Виведіть відповідь для кожного символа-центру через пробіл

Приклад вхідних даних-1

abcd

Приклад вихідних даних-1

1 1 1 1

Приклад вхідних даних-2

aaaaa

Приклад вихідних даних-2

1 3 5 3 1