e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

2013 Petrozavodsk, February 2

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 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?

Input

The only line of input contains the string s1...sn where si are small English letters (1n105).

Output

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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
aba
Output example #1
1 2 3
Author M.Rubinchik, G.Nazarov
Source 2013 Petrozavodsk, Winter, Ural FU contest, Kontur Cup, Problem J