Після того як Міша розв'язав на Тімусі сімь задач зі словом "паліндром" у назві, він набув незвичайну здібність. Тепер, прочитавши слово, він може порахувати у думках кількість унікальных непорожніх підрядків цього слова, які є паліндромами. Діма хоче перевірити, чи не помиляється Міша. Для цього він дописує до слова по одній букві \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}.