给定一个由 $n$ 个小写英文字母组成的字符串 $S$，其重复函数 $f_S(x)$ 定义如下:

• 对于正整数 1$ \leq i \leq n$， $f_S(i)$ 的值是字符串 $S$ 的一个最长子字符串 $A$，它可以将给定字符串 $S$ 表示为 $S = A\#A\# \cdots A \#A$，其中字符串 $A$ 恰好出现 $i$ 次，而其中的 $\#$ 可以是任意字符串（包括空串）。如果不存在满足要求的子字符串 $A$，则 $f_{S}(i)$ 为空串。

重复函数问题：对于给定的由 $n$ 个小写英文字母组成的字符串 $S$，计算函数 $f_{S}(i)$ 的值，及其长度 $|f_{S}(i)|$，$2 \leq i \leq n$。

输入格式

测试数据的第一行有一个由小写英文字母组成的字符串 $S$。

输出格式

依次输出给定的字符串 $S$ 的 $n − 1$ 个子串 $f_{S}(i)$ 的长度 $f_S(i)$，$2 \leq i \leq n$。

样例数据

样例输入

abaabacdabaaba

样例输出

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

子任务

测试数据中 $10\%$ 的数据满足 $n \leq 300$ 。

测试数据中 $30\%$ 的数据满足 $n \leq 3\,000$ 。

测试数据中 $80\%$ 的数据满足 $n \leq 200\,000$ 。

测试数据中 $100\%$ 的数据满足 $n \leq 1\,000\,000$ 。