After solving seven problems on Timus Online Judge with a word
“palindrome” in the problem name, Misha has got an unusual ability.
Now, when he reads a word, he can mentally count the number of unique
nonempty substrings of this word that are palindromes.
Dima wants to test Misha’s new ability. He adds letters s1, ...,
sn to a word, letter by letter, and after every letter asks Misha, how
many different nonempty palindromes current word contains as substrings.
Which n numbers will Misha say, if he will never be wrong?
The only line of input contains the string s1...sn, where si are
small English letters (1 ≤ n ≤ 105).
Output n numbers separated by whitespaces, i-th of these numbers
must be the number of different nonempty substrings of prefix s1...si
that are palindromes.
Problem Author: Mikhail Rubinchik (prepared by Grigory Nazarov)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013