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