После того как Миша решил на Тимусе семь задач со словом "палиндром" в названии, он приобрёл необыкновенную способность. Теперь, прочитав слово, он может посчитать в уме количество уникальных непустых подстрок этого слова, являющихся палиндромами. Дима хочет проверить, не ошибается ли Миша. Для этого он дописывает к слову по одной букве \textbf{s_1}, ..., \textbf{s_n} и после каждой буквы просит Мишу сказать, сколько различных непустых подстрок-палиндромов содержит слово в данный момент. Какие \textbf{n} чисел назовёт Миша, если он действительно никогда не ошибается? \InputFile На вход подаётся строка \textbf{s_1...s_n} (\textbf{1 }≤ \textbf{n }≤ \textbf{10^5}) из строчных латинских букв. \OutputFile Выведите \textbf{n }чисел через пробел. \textbf{i}-е число должно равняться количеству различных подстрок-палиндромов префикса \textbf{s_1...s_i}.