题目描述

设字符串 $s$ 的长度为 $n$。对于每个 $k=1,2,\dots,n$，求 $s$ 的所有非空子串中，$k$ 级回文串的数量。

定义如下：

• 字符串正着读和倒着读相同，当且仅当它是 $1$ 级回文串；
• 对于 $k>1$，若一个字符串的左半部分和右半部分相同，并且这两个半部分都是非空的 $(k-1)$ 级回文串，则它是 $k$ 级回文串。

长度为奇数时，左半部分是长度为 $\lfloor |t|/2\rfloor$ 的前缀，右半部分是同样长度的后缀，中间字符不属于任何一半。

同一个内容相同但位置不同的子串应分别计数。例如在字符串 aaa 中，单字符子串 a 出现了 $3$ 次。

输入格式

输入一行字符串 $s$（$1 \le |s| \le 5000$），只包含小写英文字母。

输出格式

输出 $n$ 个整数。第 $k$ 个整数表示 $s$ 的非空子串中 $k$ 级回文串的数量。

样例

样例 1

输入：

abba

输出：

6 1 0 0

样例 2

输入：

abacaba

输出：

12 4 1 0 0 0 0