Palindromic Characteristics of Substrings

Define a function \( f(x) \) for a string \( x \) as follows:

• If \( |x|=1 \), then \( f(x)=1 \).
• If \( x \) is not a palindrome, then \( f(x)=0 \).
• If \( x \) is a palindrome, let \( y \) be the string formed by the first \( \frac{|x|+1}{2} \) characters of \( x \). Then, \( f(x)=f(y)+1 \).

Given a string \( s \) and an integer \( k \), count for every non-empty substring \( x \) of \( s \) the number of times \( f(x)=i \) for each \( i \) from \( 1 \) to \( k \) (if \( f(x) \) is greater than \( k \), it is ignored).

inputFormat

The input consists of two lines:

1. The first line contains a non-empty string \( s \) consisting of lowercase English letters.
2. The second line contains an integer \( k \) (\( 1 \le k \le |s| \)).

outputFormat

Output \( k \) space-separated integers. The \( i\)-th integer indicates the count of non-empty substrings \( x \) of \( s \) such that \( f(x)=i \).

sample

aaa
2

3 2