Rikka 最近得到了一个魔法盒。盒子里有 $n$ 个排成一行的方格，每个方格里都有一个小写英文字母。作为一名魔法师，Rikka 可以对这些方格施法，赋予它们魔力。

首先，她可以选择一个连续的方格区间，并使用特定的咒语赋予这些方格“光明之力”。咒语就是所选方格区间内字母的连接。例如，如果 Rikka 选择了一个从左到右依次写有字母 'a'、'b' 和 'c' 的方格区间，那么咒语就是 "abc"。

其次，她可以选择一个连续的方格区间（可以与之前相同，也可以不同），并使用特定的咒语赋予这些方格“黑暗之力”。咒语同样是所选方格内字母的连接。

最后，同时拥有两种力量的方格将被激活。

Rikka 希望两次使用的咒语完全相同。她想知道，对于 $0$ 到 $n$ 之间的每个数字 $k$，有多少种方法可以使两次咒语相同且恰好激活 $k$ 个方格。你能帮帮她吗？

输入格式

输入的第一行包含一个由小写英文字母组成的字符串 $s$。字符串的第 $i$ 个字母表示从左往右数第 $i$ 个方格中的字母。字符串的长度在 $1$ 到 $5 \cdot 10^5$ 之间。

输出格式

输出一行，包含 $n+1$ 个整数，其中第 $i$ 个整数表示恰好激活 $i-1$ 个方格的方法数。这里 $n$ 是输入字符串的长度。

样例

样例输入 1

aaaaa

样例输出 1

13 9 6 4 2 1