You like strings. Someone has given you a string consisting only of lowercase letters.

Since you are an excellent Oler, you decide to conduct research on this string.

Two strings are defined as similar if and only if there exists at most one $i$ such that the two strings differ only at the $i$-th character.

You extract all substrings of length $m$ from this string. You want to know, for each substring of length $m$, how many other substrings of length $m$ are similar to it.

Input

The first line contains two positive integers $n, m$, representing the length of the string and the length of the substrings you extracted.

The next line contains a string of length $n$ consisting only of lowercase letters.

Output

Output a single line containing $n - m + 1$ integers, where the $i$-th integer represents how many substrings are similar to the $i$-th substring (excluding the $i$-th substring itself).

Examples

Input 1

8 3
aabaabab

Output 1

2 1 1 2 1 3

Subtasks

Subtask 1 (10%): $1 \le n \le 500$;

Subtask 2 (20%): $1 \le n \le 5000$;

Subtask 3 (30%): $1 \le n \le 10^5$, $1 \le m \le 100$.

Subtask 4 (40%): No special restrictions.

For 100% of the data, $1 \le n \le 10^5$, $1 \le m \le n$.