差异

对于两个长度相等的字符串 $s,t$，若 $s,t$ 不同的位数不超过 $k$，则称 $(s,t)$ 关系很好。

现在给定长度为 $n$ 的字符串 $S$，对于每个 $1\le i\le n-1$，记字符串 $A$ 为 $S$ 的前 $i$ 位，$B$ 为 $S$ 的后 $n-i$ 位。

现在 $a,b$ 分别为 $A,B$ 的子串，求出有多少对 $(a,b)$ 关系很好。

输入格式

第一行两个整数 $n,k$，意义如题述。

第二行一个字符串 $S$。

输出格式

共 $n-1$ 行，每行一个整数，表示答案。

样例

输入样例 1

4 0
abca

输出样例 1

1
1
1

样例 1 说明

一直都有且仅有 $(\texttt a,\texttt a)$ 关系很好。

输入样例 2

6 1
abcadd

输出样例 2

5
9
10
8
5

数据规模与约定

• 测试点 $1$：$S$ 仅由一种字符构成；
• 测试点 $2\sim 3$：$n\le 10$；
• 测试点 $4\sim 6$：$n\le 100$。
• 测试点 $7\sim 10$：无特殊限制。

对于所有数据，$2\le n\le 3\times 10^3$，$0\le k\le 3\times 10^3$。且 $S$ 仅由小写字母构成。