Problem Description

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

• If $x$ has length $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 consisting of the first $\frac{|x|+1}{2}$ characters of $x$. Then $f(x)=f(y)+1$.

Given a string $s$ and an integer $k$, for every non-empty substring of $s$, count how many substrings have $f$ equal to each value from $1$ to $k$.

Input Format

The first line contains two integers $N(1\leq N\leq 10^5)$ and $k(1\leq k\leq 30)$.

The next line contains a string $s$ of length $N$, consisting only of lowercase letters.

Output Format

Output the answers for each value from $1$ to $k$.

4 3
bbab

5 1 0 

3 3
bbb

3 2 1 

Hint

Translated by ChatGPT 5