После того как Миша решил на Тимусе семь задач со словом «палиндром» в названии, он приобрёл необыкновенную способность. Теперь, прочитав слово, он может посчитать в уме количество уникальных непустых подстрок этого слова, являющихся палиндромами.

Дима хочет проверить, не ошибается ли Миша. Для этого он дописывает к слову по одной букве s₁, ..., s_n и после каждой буквы просит Мишу сказать, сколько различных непустых подстрок-палиндромов содержит слово в данный момент. Какие n чисел назовёт Миша, если он действительно никогда не ошибается?

На вход подаётся строка s₁...s_n из строчных латинских букв (1 ≤ n ≤ 10⁵).

Выведите n чисел через пробел. i-е число должно равняться количеству различных подстрок-палиндромов префикса s₁...s_i.