题目描述

给你一个串，让你求出长度为 $k$ 的回文子串有多少个。

给出字符串 $s$，记 $n$ 为字符串的长度，对 $k=1\sim n$ 分别求出长度 $k$ 的回文子串的个数。（位置不同就算是不同的子串）

输入格式

$1$ 行，包含 $1$ 个字符串 $s$。

输出格式

用 $1$ 行输出 $n$ 个整数，第 $i$ 个整数表示长度 $i$ 的回文子串的数量。数之间用空格分隔。

说明与提示

在第一个样例中，回文子串有 a、b、b、a、bb、abba。

abba

4 1 0 1

abacaba

7 0 3 0 1 0 1

sjjs

4 1 0 1

数据范围与约定

字符串 $s$ 只含小写英文字母，记 $n$ 是字符串长度，$1\le n\le5000$。