markdown

D. 回文特性

对于长度为 $|s|$ 的字符串 $s$，其回文特性是一个由 $|s|$ 个整数组成的序列，其中第 $k$ 个数是 $s$ 中所有非空子串中 $k$ 阶回文子串的总数。

• 一个字符串是 $1$ 阶回文，当且仅当它正着读和反着读相同。
• 一个字符串是 $k$ 阶回文（$k > 1$），当且仅当：
  • 它的左半部分等于右半部分。
  • 它的左半部分和右半部分都是非空的 $(k-1)$ 阶回文。

字符串 $t$ 的左半部分是其长度为 $\lfloor |t| / 2 \rfloor$ 的前缀，右半部分是其长度相同的后缀。其中 $\lfloor |t| / 2 \rfloor$ 表示将字符串 $t$ 的长度除以 $2$ 后向下取整。

注意：每个子串在字符串中出现多少次，就被计算多少次。例如，在字符串 "aaa" 中，子串 "a" 出现了 $3$ 次。

输入

第一行包含一个字符串 $s$（$1 \le |s| \le 5000$），由小写英文字母组成。

输出

输出 $|s|$ 个整数 —— 字符串 $s$ 的回文特性。

样例

输入样例 1

abba

输出样例 1

6 1 0 0

输入样例 2

abacaba

输出样例 2

12 4 1 0 0 0 0

注释

在第一个样例中，$1$ 阶回文子串有："a"、"b"、"b"、"a"、"bb"、"abba"；子串 "bb" 是 $2$ 阶回文。这里没有 $3$ 阶和 $4$ 阶回文子串。