Прыжки
Прапор и Ковальски обожают прыгать по льдинкам. Однажды они установили на воде друг за другом льдинок, раскрашенных в какие-то цвета. Прапору нравится прыгать через льдинки, но Ковальски очень привередлив — ему нравится прыгать через отрезок льдинок только в случае, если прыгая в одну и обратную сторону, цвета льдинок, мимо которых пролетает Ковальски, идут в одинаковом порядке (отрезок льдинок выглядит одинаково при просмотре слева направо и наоборот). Прапор и Ковальски решили выбрать некоторую льдинку и прыгать в сторону увеличения номеров льдинок. Сначала они прыгнули на одну льдинку вперёд и обратно, затем на две и обратно, так они прыгали до тех пор, пока Ковальски нравилось перепрыгивать через очередной отрезок льдинок и их хватало, чтобы сделать очередной прыжок. Пингвинов заинтересовала для каждой позиции длина первого отрезка льдинок, который Ковальски не захочет перепрыгнуть.
Входные данные
Во входном файле задается единственная строка длиной N (1 ≤ N ≤ 10^5) — раскраска льдинок в порядке увеличения номеров. Строка состоит из строчных латинских букв, различные символы соответствуют различным цветам льдинок, одинаковые — одинаковым. Строка оканчивается символом перевода строки.
Выходные данные
В единственной строке выходного файла выведите N целых неотрицательных чисел a_i — длина первого отрезка, который не захочет перепрыгнуть Ковальски в позиции i.