题目描述

给出一个由小写字母组成字符串 $S(|S|<=250000)$，令 $F(x)$ 表示 $S$ 的所有长度为 $x$ 的子串中，出现次数的最大值。

求: $F(1) \dots F(Length(S))$。

输入格式

一行一个字符串。

输出格式

输出 $|S|$ 行，第 $i$ 行为 $F(i)$ 的值。

输入输出样例 #1

输入 #1

ababa

输出 #1

3
2
2
1
1