I. Palindrome
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Palindromes are very interesting! However, asking you to simply print whether a string is a palindrome or not would make life too easy.

Let us, then, define how to calculate the degree of a palindrome. There are three possible cases, as follows:

  • For a given string $$$s$$$, if $$$s$$$ is not a palindrome, then its degree will be $$$0$$$.
  • For a given string $$$s$$$, if $$$s$$$ has length one, then its degree will be $$$1$$$.
  • For a given string $$$s$$$, if $$$s$$$ is a palindrome of a length greater than one, then its degree will be the degree of its left half (middle character included in case the length of $$$s$$$ is an odd number) plus one.

For instance, string $$$abc$$$ has degree $$$0$$$ since it is not a palindrome, string $$$a$$$ is a palindrome of degree 1 since it contains only one character, and $$$ababa$$$ is a palindrome of degree 2 since $$$aba$$$ is a palindrome of degree 1.

You are given a string $$$s (1 \leq |s| \leq 10^5)$$$ and an integer $$$k$$$. For every $$$i = \overline{1, k}$$$, you should answer how many substrings of $$$s$$$ have degree $$$i$$$. Please note that a substring is formed of characters that are on consecutive positions in $$$s$$$.

Input

The first line of input will contain string $$$N (1 \leq N \leq 10^5)$$$, the length of the string, and $$$K (1 \leq K \leq 30)$$$, the maximum degree that you should compute the answer for.

The second line of input will contain the string $$$s$$$, containing only lowercase letters of the Latin alphabet.

Output

The output should be formed of one line, containing the answers for the $$$K$$$ degrees, starting with the answer for degree $$$1$$$ and ending with the answer for the $$$K^{th}$$$ degree, separated by spaces.

Examples
Input
4 3
bbab
Output
5 1 0
Input
3 3
bbb
Output
3 2 1