Identifying the Victory Gene

Farmer John believes that Bessie’s string of triumphs isn’t by chance – it must be written in her DNA. To verify this, he examines Bessie’s genome represented by a string \(S\) of length \(N\) (where \(1 \le N \le 3000\)). For a chosen pair \((K, L)\) satisfying \(1 \le L \le K \le N\), he considers every contiguous substring of \(S\) of length \(K\) (called a K-mer). From each K-mer, he extracts every contiguous substring of length \(L\) and designates the lexicographically smallest one (if there is a tie, he picks the one occurring first) as the "victory gene candidate" for that K-mer. He then records the candidate’s starting position (0-indexed) in a set \(P\) (thus duplicates are counted only once).

Since Farmer John has not finally chosen \(K\) and \(L\), he wants to know how many pairs \((K, L)\) yield a candidate set \(P\) of a given size. More precisely, for each integer \(v\) from \(1\) to \(N\), determine the number of pairs \((K, L)\) that result in \(|P| = v\).

Note: All formulas are expressed in LaTeX format.

inputFormat

The input consists of a single line containing the string \(S\), representing the genome. \(S\) has length \(N\) where \(1 \le N \le 3000\).

outputFormat

Output a single line containing \(N\) space‐separated integers. The \(v\)th integer (1-indexed) should be the number of pairs \((K, L)\) for which the candidate set \(P\) has size \(v\).

sample

A

1