CF1858D.Trees and Segments

The teachers of the Summer Informatics School decided to plant $n$ trees in a row, and it was decided to plant only oaks and firs. To do this, they made a plan, which can be represented as a binary string $s$ of length $n$. If $s_i = 0$, then the $i$-th tree in the row should be an oak, and if $s_i = 1$, then the $i$-th tree in the row should be a fir.

The day of tree planting is tomorrow, and the day after tomorrow an inspector will come to the School. The inspector loves nature very much, and he will evaluate the beauty of the row as follows:

• First, he will calculate $l_0$ as the maximum number of consecutive oaks in the row (the maximum substring consisting of zeros in the plan $s$). If there are no oaks in the row, then $l_0 = 0$.
• Then, he will calculate $l_1$ as the maximum number of consecutive firs in the row (the maximum substring consisting of ones in the plan $s$). If there are no firs in the row, then $l_1 = 0$.
• Finally, he will calculate the beauty of the row as $a \cdot l_0 + l_1$ for some $a$ — the inspector's favourite number.

The teachers know the value of the parameter $a$, but for security reasons they cannot tell it to you. They only told you that $a$ is an integer from $1$ to $n$.

Since the trees have not yet been planted, the teachers decided to change the type of no more than $k$ trees to the opposite (i.e., change $s_i$ from $0$ to $1$ or from $1$ to $0$ in the plan) in order to maximize the beauty of the row of trees according to the inspector.

For each integer $j$ from $1$ to $n$ answer the following question independently:

• What is the maximum beauty of the row of trees that the teachers can achieve by changing the type of no more than $k$ trees if the inspector's favourite number $a$ is equal to $j$?

暑期信息学学校（SIS）的老师们决定在一排种植 $n$ 棵树，且只种植橡树和冷杉。为此，他们制定了一份计划，该计划可用一个长度为 $n$ 的二进制字符串 $s$ 表示：若 $s_i = 0$，则第 $i$ 棵树应为橡树；若 $s_i = 1$，则第 $i$ 棵树应为冷杉。

植树日是明天，而大后天将有检查员来校视察。检查员非常热爱自然，他将按如下方式评估这一排树木的“美观度”：

• 首先，他计算 $l_0$，即该排中连续橡树的最大数目（即计划字符串 $s$ 中最长的全 $0$ 子串的长度）。若该排中没有橡树，则 $l_0 = 0$。
• 然后，他计算 $l_1$，即该排中连续冷杉的最大数目（即计划字符串 $s$ 中最长的全 $1$ 子串的长度）。若该排中没有冷杉，则 $l_1 = 0$。
• 最后，他将该排的美观度定义为 $a \cdot l_0 + l_1$，其中 $a$ 是检查员最钟爱的一个数。

老师们知道参数 $a$ 的值，但出于安全原因，他们不能告诉你。他们仅告知你：$a$ 是介于 $1$ 到 $n$（含）之间的整数。

由于树木尚未种植，老师们决定最多将 $k$ 棵树的种类改为相反类型（即在计划中将 $s_i$ 由 $0$ 改为 $1$ 或由 $1$ 改为 $0$），以使该排树木在检查员眼中达到最大美观度。

对每个从 $1$ 到 $n$ 的整数 $j$，请独立回答以下问题：

• 若检查员最钟爱的数 $a$ 恰好等于 $j$，那么老师们最多更改 $k$ 棵树的种类所能达到的最大美观度是多少？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 3000$, $0 \le k \le n$) — the number of trees in the row and the maximum number of changes.

The second line contains a string $s$ of length $n$, consisting of zeros and ones — the plan description.

It is guaranteed that the sum of all $n$ values for all test cases does not exceed $3000$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 3000$，$0 \le k \le n$）—— 行中树的棵数以及最多允许的修改次数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 0 和 1 组成 —— 计划描述。

保证所有测试用例的 $n$ 值之和不超过 $3000$。

For each test case, print $n$ integers, the $j$-th ($1 \le j \le n$) of which is the maximum beauty of the row of trees after no more than $k$ changes if $a = j$ is used to calculate the beauty.

对于每个测试用例，输出 $n$ 个整数，其中第 $j$ 个整数（$1 \le j \le n$）表示：当使用 $a = j$ 计算美观度时，在最多进行 $k$ 次修改后，树行所能达到的最大美观度。

In the first test case no changes are allowed, so $l_0 = 0$ and $l_1 = 3$ always hold. Thus, regardless of the value of $a$, the beauty of the row of trees will be $3$.

In the second test case for $a \in {1, 2}$ the teachers can, for example, change the plan $s$ to $0111$ (by changing $s_4$), and for $a \in {3, 4}$ — to $0010$ (by changing $s_2$). In this case, the beauty of the row for each $a$ is calculated as follows:

• For $a = 1$: $l_0 = 1$, $l_1 = 3$. The beauty of the row is $1\cdot 1 + 3 = 4$.
• For $a = 2$: $l_0 = 1$, $l_1 = 3$. The beauty of the row is $2\cdot 1 + 3 = 5$.
• For $a = 3$: $l_0 = 2$, $l_1 = 1$. The beauty of the row is $3\cdot 2 + 1 = 7$.
• For $a = 4$: $l_0 = 2$, $l_1 = 1$. The beauty of the row is $4\cdot 2 + 1 = 9$.

It can be shown that the changes described above are optimal for all $a$ from $1$ to $4$.

在第一个测试用例中，不允许进行任何修改，因此始终有 $l_0 = 0$ 且 $l_1 = 3$。于是，无论 $a$ 取何值，该排树木的美观度恒为 $3$。

在第二个测试用例中，当 $a \in \{1, 2\}$ 时，教师们可以（例如）将计划字符串 $s$ 修改为 $0111$（通过修改 $s_4$）；而当 $a \in \{3, 4\}$ 时，则可将其修改为 $0010$（通过修改 $s_2$）。此时，对每个 $a$ 值，该排树木的美观度计算如下：

• 当 $a = 1$ 时：$l_0 = 1$，$l_1 = 3$，该排树木的美观度为 $1\cdot 1 + 3 = 4$。
• 当 $a = 2$ 时：$l_0 = 1$，$l_1 = 3$，该排树木的美观度为 $2\cdot 1 + 3 = 5$。
• 当 $a = 3$ 时：$l_0 = 2$，$l_1 = 1$，该排树木的美观度为 $3\cdot 2 + 1 = 7$。
• 当 $a = 4$ 时：$l_0 = 2$，$l_1 = 1$，该排树木的美观度为 $4\cdot 2 + 1 = 9$。

可以证明，上述修改方案对所有 $a \in \{1, 2, 3, 4\}$ 均是最优的。