对于一个长度为 $n \ge 1$ 的字符串 $S$ 和一个正整数 $k$ ($1 \le k \le n$)，如果 $S$ 的一个非空子串恰好出现了 $k$ 次，则称该子串为 $k$-子串。这 $k$ 次出现不一定是不相交的，即可能存在重叠。例如，若 $S = \text{"ababa"}$，则对于每个 $k = 1, \dots, 5$，$S$ 的 $k$-子串如下：

• $S$ 中有四个 1-子串："abab"、"ababa"、"bab" 和 "baba"，因为这些子串在 $S$ 中恰好出现一次。注意 "aba" 不是 1-子串，因为它出现了两次。
• $S$ 中有四个 2-子串："ab"、"aba"、"b" 和 "ba"。子串 "ab" 恰好出现两次且不重叠。子串 "aba" 的两次出现共用了一个字符 "a"，但它没有出现三次或更多。
• $S$ 中只有一个 3-子串："a"。
• $S$ 中不存在 4-子串或 5-子串。

对于 $S$ 的一个 $k$-子串 $T$，令 $d(T)$ 为 $T$ 在 $S$ 中互不重叠出现的最大次数。例如，2-子串 $T = \text{"ab"}$ 可以不重叠地选出两次，即互不重叠出现的最大次数为 2，因此 $d(T) = 2$。对于 2-子串 $T = \text{"aba"}$，它无法不重叠地选出两次，因此 $d(T) = 1$。对于 3-子串 $T = \text{"a"}$，它可以不重叠地选出三次，这是最大值，因此 $d(T) = 3$。

令 $f(k)$ 为所有满足 $d(T)$ 最大的 $k$-子串 $T$ 中的最长长度，其中 $1 \le k \le n$。例如，对于 $S = \text{"ababa"}$，$k = 1, \dots, 5$ 时的 $f(k)$ 如下：

• 对于 $k = 1$，所有 1-子串 $T$ 均只能不重叠地选出一次，即 $d(T) = 1$。因此，所有 $d(T) = 1$ 的 1-子串中最长的是 "ababa"，故 $f(1) = 5$。
• 对于 $k = 2$，对于 $T = \text{"aba"}$，$d(T) = 1$，而对于其他 2-子串 $T = \text{"ab"}$、"b"、"ba"，$d(T) = 2$。在所有 $d(T) = 2$ 的 2-子串中，"ab" 和 "ba" 是最长的，故 $f(2) = 2$。
• 对于 $k = 3$，$f(3) = 1$，因为只有一个 3-子串 "a"。
• 对于 $k = 4, 5$，不存在 $k$-子串，故 $f(4) = 0$ 且 $f(5) = 0$。

给定一个长度为 $n$ 的字符串 $S$，编写一个程序，输出从 $k = 1$ 到 $k = n$ 的 $n$ 个 $f(k)$ 值。对于上述例子，输出应为 5 2 1 0 0。

输入格式

程序从标准输入读取数据。输入的第一行包含一个由 $n$ ($1 \le n \le 50,000$) 个小写字母组成的字符串 $S$。

输出格式

程序向标准输出写入数据。输出一行，包含 $n$ 个非负整数，用空格分隔，依次表示 $f(1), f(2), \dots, f(n)$。注意，如果对于某个 $k$ 不存在 $k$-子串，则 $f(k)$ 应为 0。

样例

样例输入 1

ababa

样例输出 1

5 2 1 0 0

样例输入 2

aaaaaaaa

样例输出 2

8 7 6 5 4 3 2 1