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