Паліндроми та суперздібності#5618
Після того як Міша розв'язав на Тімусі сім задач зі словом "паліндром" у назві, він набув незвичайної здібності. Тепер, прочитавши слово, він може порахувати у думках кількість унікальних непорожніх підрядків цього слова, які є паліндромами.
Діма хоче перевірити, чи не помиляється Міша. Для цього він дописує до слова по одній букві s_1, \ldots, s_n і після кожної букви просить Мішу сказати, скільки різних непорожніх паліндромних підрядків містить слово у даний момент. Які чисел назве Міша, якщо він дійсно ніколи не помиляється?
На вхід подається рядок s_1 \ldots s_n, де s_i — малі латинські літери (1 \le n \le 10^5).
Виведіть чисел, розділених пробілами. -те число повинно дорівнювати кількості різних непорожніх паліндромних підрядків префікса s_1 \ldots s_i.
Приклад 1