eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Прыжки

Прыжки

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Прапор и Ковальски обожают прыгать по льдинкам. Однажды они установили на воде друг за другом льдинок, раскрашенных в какие-то цвета. Прапору нравится прыгать через льдинки, но Ковальски очень привередлив — ему нравится прыгать через отрезок льдинок только в случае, если прыгая в одну и обратную сторону, цвета льдинок, мимо которых пролетает Ковальски, идут в одинаковом порядке (отрезок льдинок выглядит одинаково при просмотре слева направо и наоборот). Прапор и Ковальски решили выбрать некоторую льдинку и прыгать в сторону увеличения номеров льдинок. Сначала они прыгнули на одну льдинку вперёд и обратно, затем на две и обратно, так они прыгали до тех пор, пока Ковальски нравилось перепрыгивать через очередной отрезок льдинок и их хватало, чтобы сделать очередной прыжок. Пингвинов заинтересовала для каждой позиции длина первого отрезка льдинок, который Ковальски не захочет перепрыгнуть.

Вхідні дані

Во входном файле задается единственная строка длиной N (1N10^5) — раскраска льдинок в порядке увеличения номеров. Строка состоит из строчных латинских букв, различные символы соответствуют различным цветам льдинок, одинаковые — одинаковым. Строка оканчивается символом перевода строки.

Вихідні дані

В единственной строке выходного файла выведите N целых неотрицательных чисел a_i — длина первого отрезка, который не захочет перепрыгнуть Ковальски в позиции i.

Приклад

Вхідні дані #1
ababb
Вихідні дані #1
2 2 2 3 2
Джерело Яндекс, відбір ЗКШ 2011-2012, 1 тур