题目描述

$\zeta$ 在论文中的一个字符串 $s$ 中，悟出了一个漫长的，复杂的人生命题。

为了让研究的错误率不超过 $5$ 分，他要对每个位置 $i$ 求出在 $i$ 之前的位置 $j$ 的个数，满足：

$$\operatorname{lcs}(s[1\dots j],s[1\dots i])=s[j+1\dots i] $$

其中 $\operatorname{lcs}(s_i,s_j)$ 表示字符串 $s_i,s_j$ 的最长公共后缀。

输入格式

一行一个仅由小写字母组成的字符串 $s$。

输出格式

一行 $|s|$ 个数，第 $i$ 个数表示 $w_i$。

aabb

0 1 0 1

cddcddcdc

0 0 1 0 0 2 0 0 1

abbcbc

0 0 1 0 0 1

zzttzttzzttztt

0 1 0 1 0 0 2 0 1 0 1 1 0 3

数据范围与提示

对于 $30\%$ 的数据，$|s|\leq 5\times 10^3$。

对于 $60\%$ 的数据，$|s|\leq 5\times 10^4$。

对于 $100\%$ 的数据，$|s|\leq 5\times 10^5$。

保证输入为小写字母组成的字符串。