Вам надано рядок довжиною \(n\). Для кожного цілого числа між \(1…n\) вам потрібно вивести кількість різних підрядків такої довжини.

Обмеження

• \(1≤n≤10^5\)

Формат вхідних даних

Єдиний вхідний рядок містить рядок довжиною \(n\), який складається із символів 'a'–'z'.

Формат вихідних даних

Для кожного цілого числа між \(1…n\) виведіть кількість різних підрядків такої довжини.

Приклад вхідних даних

abab

Приклад вихідних даних

2 2 2 1