题目描述

定义一个 $k$ 阶回文串 $s$：

• 如果 $k = 1$，那么 $s$ 为回文串。
• 否则，$s$ 的前半部分与后半部分为相等的 $k - 1$ 阶回文串。

$s$ 的前半部分与后半部分是其长度为 $\lfloor \frac{|s|} 2 \rfloor$ 的前（后）缀。

给定字符串 $s$，对于 $1 \leq i \leq |s|$，依次输出 $s$ 的 $i$ 阶回文子串的个数。

输入格式

一行一个字符串 $s$，$1 \le |s| \le 5000$。

输出格式

输出 $|s|$ 个整数，依次表示 $s$ 的 $i$ 阶回文子串的个数。

abba

6 1 0 0

abacaba

12 4 1 0 0 0 0