Counting Distinct Substrings by Frequency

Given a string \(S\) consisting of only lowercase English letters, count for each integer \(f\) (where \(1 \le f \le |S|\)) how many distinct substrings of \(S\) appear exactly \(f\) times.

Two substrings are considered different if they have different lengths or differ in at least one character.

Formally, for each \(f\) from 1 to \(|S|\), let \(ans[f]\) be the number of distinct substrings that appear exactly \(f\) times in \(S\). Output \(ans[1], ans[2], \dots, ans[|S|]\) separated by spaces.

inputFormat

A single line containing the string (S) (only lowercase English letters).

outputFormat

Output (|S|) integers separated by spaces, where the (i)-th integer is the number of distinct substrings that appear exactly (i) times in (S).

sample

abc

6 0 0