Palindromes and Super Abilities#5618
After solving seven problems on the Timus Online Judge with the word "palindrome" in the problem name, Misha has acquired 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 appends letters s_1, \ldots, s_n to a word one by one, and after each letter asks Misha how many different nonempty palindromic substrings the current word contains. Which numbers will Misha say, if he is always correct?
The only line of input contains the string s_1 \ldots s_n, where s_i are lowercase English letters (1 \le n \le 10^5).
Output numbers, separated by spaces. The -th number must be the number of different nonempty palindromic substrings of the prefix s_1 \ldots s_i.
Example 1