Hold the Line!

In the Middle Ages, war was not an extraordinary event. Many states were instead at constant war with their neighbors for decades. Peaceful times were rare, and not everyone lived to see them.

As science advanced, its results were applied to warfare. New weapons and battle tactics appeared, and field medicine developed. Scientific methods were also used to choose the squad sent on each mission.

Before a commander picked a squad for battle, he lined up all the soldiers under his command in a row. Then he chose the soldier who would lead the squad, and only after that chose the squad itself.

According to the latest research by British alchemists, a squad had to consist of an odd number of soldiers standing consecutively in the row. The squad leader had to be the soldier standing in the middle of the chosen group. The last condition was that the first letter of the name of the $k$-th soldier from the left in the squad had to match the first letter of the name of the $k$-th soldier from the left in the whole row. The alchemists guaranteed victory in any battle when all these requirements were met, so the requirements were enforced strictly.

Following tradition and the principle that "quantity turns into quality," commanders usually gave their leader the most suitable squad under these constraints. Your task is to take the first letters of the names of the soldiers in the row and find, for each soldier, the maximum size of a squad he can command.

The first line of the input file contains the string $S$, the first letters of the names of the soldiers in the row. The length of the string does not exceed $500{\,}000$. The string consists only of lowercase Latin letters.

The first line of the output file contains $|S|$ integers separated by spaces. The $i$-th integer is the maximum size of a squad that the soldier at position $i$ can command.