ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2040. Palindromes and Super Abilities 2

Time limit: 0.5 second
Memory limit: 100 MB
Dima adds letters s1, …, sn one by one to the end of a word. After each letter, he asks Misha to tell him how many new palindrome substrings appeared when he added that letter. Two substrings are considered distinct if they are different as strings. Which n numbers will be said by Misha if it is known that he is never wrong?

Input

The input contains a string s1sn consisting of letters ‘a’ and ‘b’ (1 ≤ n ≤ 5 000 000).

Output

Print n numbers without spaces: i-th number must be the number of palindrome substrings of the prefix s1si minus the number of palindrome substrings of the prefix s1si−1. The first number in the output should be one.

Sample

inputoutput
abbbba
111111

Notes

We guarantee that jury has C++ solution which fits Time Limit at least two times. We do not guarantee that solution on other languages exists (even Java).
Problem Author: Mikhail Rubinchik (prepared by Kirill Borozdin)
Problem Source: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014