대열을 지켜라!

중세에는 전쟁이 특별한 사건이 아니었다. 오히려 많은 나라가 수십 년 동안 이웃 나라와 계속 전쟁 상태에 있었다. 평화로운 시기는 드물어서, 살아생전에 그런 시기를 겪지 못하는 사람도 많았다.

과학이 발전하면서 그 성과가 군사 분야에도 도입되었다. 새로운 무기와 전투 전술이 등장했고, 야전 의학도 발전했다. 과학적인 방법은 임무에 나갈 부대를 고르는 데에도 쓰였다.

지휘관은 전투에 나설 부대를 고르기 전에 자신이 거느린 모든 병사를 한 줄로 세운다. 그다음 부대를 이끌 병사를 정하고, 그 병사를 기준으로 부대를 정한다.

당시 영국 연금술사들의 최신 연구에 따르면, 부대는 줄에서 연속해서 나란히 선 홀수 명의 병사로 구성되어야 했다. 부대장은 선택된 병사들의 가운데에 선 병사여야 했다. 마지막 조건은 부대의 왼쪽에서 $k$번째 병사의 이름 첫 글자가, 전체 줄의 왼쪽에서 $k$번째 병사의 이름 첫 글자와 같아야 한다는 것이었다. 연금술사들은 이 조건을 모두 지키면 어떤 전투에서도 승리한다고 보장했으므로, 조건은 엄격하게 지켜졌다.

전통에 따라, 그리고 '양이 질로 바뀐다'는 원칙에 따라, 지휘관은 보통 조건에 가장 잘 맞는 연금술사 부대를 부대장에게 맡겼다. 여러분이 해야 할 일은 줄에 선 병사들의 이름 첫 글자가 주어졌을 때, 각 병사가 지휘할 수 있는 부대의 최대 크기를 구하는 것이다.

입력 파일의 첫 줄에는 줄에 선 병사들의 이름 첫 글자로 이루어진 문자열 $S$가 주어진다. 문자열의 길이는 $500{\,}000$을 넘지 않는다. 문자열은 영문 소문자로만 이루어져 있다.

출력 파일의 첫 줄에 공백으로 구분된 $|S|$개의 정수를 출력한다. $i$번째 정수는 위치 $i$의 병사가 지휘할 수 있는 부대의 최대 크기이다.