给定一个由 $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$ 。