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 \textbf{s_1}, ..., \textbf{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 \textbf{n} numbers will Misha say, if he will never be wrong? \InputFile The only line of input contains the string \textbf{s_1...s_n} where \textbf{s_i} are small English letters (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}). \OutputFile Output \textbf{n} numbers separated by whitespaces, \textbf{i}-th of these numbers must be the number of different nonempty substrings of prefix \textbf{s_1...s_i} that are palindromes.