Паліндроми та суперздібності

Після того як Міша розв'язав на Тімусі сімь задач зі словом "паліндром" у назві, він набув незвичайну здібність. Тепер, прочитавши слово, він може порахувати у думках кількість унікальных непорожніх підрядків цього слова, які є паліндромами.

Діма хоче перевірити, чи не помиляється Міша. Для цього він дописує до слова по одній букві s_1, ..., s_n і після кожної букви просить Мішу сказати, скільки різних непорожніх підрядків-паліндромів містить слово у даний момент. Які n чисел назве Міша, якщо він дійсно ніколи не помиляється?

Вхідні дані

На вхід подається рядок s_1...s_n (1 ≤ n ≤ 10^5) з рядкових латинських букв.

Вихідні дані

Виведіть n чисел через пропуск. i-те число повинно дорівнювати кількості різних підрядків-паліндромів префікса s_1...s_i.

Приклади