树木与线段

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

有一排 $n$ 棵树，种植计划用长度为 $n$ 的二进制串 $s$ 表示。$s_i=0$ 表示第 $i$ 棵是橡树，$s_i=1$ 表示第 $i$ 棵是冷杉。

检查员会计算：

• $l_0$：最长连续 0 子串的长度；若没有 0，则为 $0$；
• $l_1$：最长连续 1 子串的长度；若没有 1，则为 $0$。

当检查员的参数为 $a$ 时，美观度为 $a\cdot l_0+l_1$。在种植前可以翻转不超过 $k$ 个字符。对于每个 $a=1,2,\ldots,n$，请独立求出能够得到的最大美观度。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n,k$，第二行包含二进制串 $s$。

输出格式

对于每组数据，输出 $n$ 个整数。第 $j$ 个整数表示 $a=j$ 时的最大美观度。

样例输入 1

5
3 0
111
4 1
0110
5 0
10000
6 2
101101
7 1
0001101

样例输出 1

3 3 3
4 5 7 9
5 9 13 17 21
6 9 13 17 21 25
7 10 13 17 21 25 29

数据范围

$1\le t\le1000$，$1\le n\le3000$，$0\le k\le n$，所有测试组的 $n$ 之和不超过 $3000$。