Palindromes and Super Abilities
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 s_1, ..., s_n 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?
Input
The only line of input contains the string s_1...s_n where s_i are small English letters (1 ≤ n ≤ 10^5).
Output
Output n numbers separated by whitespaces, i-th of these numbers must be the number of different nonempty substrings of prefix s_1...s_i that are palindromes.