29330번 - Держать строй! 다국어

Как известно, в средние века война не была экстраординарным событием. Напротив, многие государства находились состоянии постоянной войны с соседями на протяжении десятков лет. Мирные же времена, наоборот, считались редкостью, и далеко не каждый человек успевал застать их за свою жизнь.

С развитием науки ее достижения внедрялись и в военное дело. Так появлялись новые виды вооружения, тактики ведения боя, развивалась полевая медицина. Применялся научный подход и при выборе отряда, который отправлялся на очередное задание.

Перед тем, как военачальник назначал отряд, которому предстоит отправиться в бой, он выстраивал в шеренгу всех солдат, которые находились в его подчинении. Затем определялся солдат, который будет командовать выбранным отрядом, после чего определялся сам отряд.

Согласно новейшим на тот момент исследованиям британских алхимиков, отряд должен был состоять из нечетного количества солдат, стоявших в строю подряд друг за другом. Кроме того, командиром отряда должен был оказаться тот солдат, который стоял в центре выбранного набора. Последнее же ограничение состояло в том, что первая буква в имени $k$-го слева солдата из выбранного отряда должна была совпадать с первой буквой в имени $k$-го слева солдата в общем строю. При выполнении всех этих требований британские алхимики гарантировали победу в любом бою, поэтому данные требования строго выполнялись.

Следуя сложившимся традициям и принципу <<Количество переходит в качество>>, после выбора командира военачальники обычно давали ему в подчинение наиболее подходящий под ограничения алхимика отряд. Вам же необходимо по данным первым буквам имен солдат, стоящих в строю, определить для каждого из них максимальный размер отряда, которым он сможет командовать.

Первая строка входного файла содержит строку $S$ --- первые буквы в именах солдат, стоящих в строю. Длина строки не превышает $500{\,}000$. Строка состоит только из строчных символов латинского алфавита.

В первой строке выходного файла выведите $|S|$ чисел, разделенных пробелами --- максимальный размер отряда, которым сможет командовать соответствующий солдат.