Migrated from Lutece 2260 qh与复读机XI

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

qh今天想杀一批复读机。

qh把最近几天的聊天记录扒了出来，用一种神奇的编码方式将聊天记录转换成了由小写字母组成的字符串。

记代表聊天记录的字符串为$S$。

对于每个$L$，qh想知道$S$中长度为$L$的子串中出现次数最多的子串的出现次数是多少，这样他就可以决定那些复读机应该被禁言多久。

检查聊天记录非常耗时，于是qh把这件事丢给了后缀复读机。

后缀复读机有一万个ddl要赶，没时间看聊天记录。

你能帮后缀复读机解决检查聊天记录的问题吗？

Input

第一行有一个仅由小写字母组成的字符串$S$，代表聊天记录。

Output

输出$|S|$个数，第$L$个数代表$S$中长度为$L$的子串的最多出现次数。

Samples

ababa

3 2 2 1 1

aabbbbaa

4 3 2 1 1 1 1 1

Constraints

$1 \leq |S| \leq 10^6$

Resources

2019 UESTC ACM Training for Search Algorithm and String