Given a string $S$ consisting of $n$ lowercase English letters, its repetition function $f_S(x)$ is defined as follows:

• For a positive integer $1 \leq i \leq n$, the value of $f_S(i)$ is the longest substring $A$ of $S$ such that $S$ can be represented as $S = A\#A\# \cdots A \#A$, where the string $A$ appears exactly $i$ times, and each $\#$ can be any string (including the empty string). If no such substring $A$ exists, $f_S(i)$ is an empty string.

Repetition Function Problem: For a given string $S$ consisting of $n$ lowercase English letters, calculate the length $|f_S(i)|$ of the function $f_S(i)$ for all $2 \leq i \leq n$.

Input

The first line of the input contains a string $S$ consisting of lowercase English letters.

Output

Output the lengths $|f_S(i)|$ for the $n-1$ substrings $f_S(i)$ in order, for $2 \leq i \leq n$.

Examples

Input 1

abaabacdabaaba

Output 1

6 3 3 1 1 1 1 0 0 0 0 0 0

Subtasks

$10\%$ of the test data satisfies $n \leq 300$.

$30\%$ of the test data satisfies $n \leq 3\,000$.

$80\%$ of the test data satisfies $n \leq 200\,000$.

$100\%$ of the test data satisfies $n \leq 1\,000\,000$.