Palindromlar və supergüclər

Mişa, Timusda "palindrom" sözü ilə yeddi məsələ həll etdikdən sonra qeyri-adi bir qabiliyyət qazandı. İndi, bir sözü oxuduqdan sonra, o, bu sözün unikal boş olmayan palindrom alt sıradlarının sayını düşüncəsində hesablaya bilir.

Dima, Mişanın səhv etmədiyini yoxlamaq istəyir. Bunun üçün o, sözü bir-bir hərf əlavə edərək s_1, ..., s_n və hər hərfdən sonra Mişadan həmin anda sözün neçə fərqli boş olmayan palindrom alt sıradını ehtiva etdiyini deməsini istəyir. Mişa həqiqətən heç vaxt səhv etmirsə, hansı n ədədləri deyəcək?

Giriş verilənləri

Girişdə s_1...s_n (1 ≤ n ≤ 10^5) kiçik latın hərflərindən ibarət bir sıradakı verilir.

Çıxış verilənləri

n ədədləri boşluqla ayıraraq çıxarın. i-ci ədəd s_1...s_i prefiksinin fərqli palindrom alt sıradlarının sayına bərabər olmalıdır.

Nümunələr