CF835D.Palindromic characteristics

Palindromic characteristics of string s with length |s| is a sequence of |s| integers, where k-th number is the total number of non-empty substrings of s which are k-palindromes.

A string is 1-palindrome if and only if it reads the same backward as forward.

A string is k-palindrome (k > 1) if and only if:

1. Its left half equals to its right half.
2. Its left and right halfs are non-empty (k - 1)-palindromes.

The left half of string t is its prefix of length ⌊|t| / 2⌋, and right half — the suffix of the same length. ⌊|t| / 2⌋ denotes the length of string t divided by 2, rounded down.

Note that each substring is counted as many times as it appears in the string. For example, in the string "aaa" the substring "a" appears 3 times.

字符串 $s$ 的回文特征（palindromic characteristics）是一个长度为 $|s|$ 的整数序列，其中第 $k$ 个数表示 $s$ 中非空的 $k$-回文子串的总数。

一个字符串是 1-回文串，当且仅当它正读与反读完全相同。

一个字符串是 $k$-回文串（$k > 1$），当且仅当满足以下两个条件：

1. 它的左半部分等于其右半部分；
2. 它的左半部分和右半部分均为非空的 $(k-1)$-回文串。

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

注意：每个子串按其在原字符串中出现的次数分别计数。例如，在字符串 "aaa" 中，子串 "a" 出现了 3 次。

The first line contains the string s (1 ≤ |s| ≤ 5000) consisting of lowercase English letters.

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

Print |s| integers — palindromic characteristics of string s.

输出 $\lfloor s \rfloor$ 个整数——字符串 $s$ 的回文特征值。

In the first example 1-palindromes are substring «a», «b», «b», «a», «bb», «abba», the substring «bb» is 2-palindrome. There are no 3- and 4-palindromes here.

在第一个例子中，1-回文子串有 «a»、«b»、«b»、«a»、«bb»、«abba»；子串 «bb» 是 2-回文。此处不存在 3-回文和 4-回文。