310604: CF1858D. Trees and Segments

D. Trees and Segmentstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$?

Input

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$.

Output

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.

ExampleInput

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

Output

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 

Note

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$.

题目大意：
夏季信息学学校的老师们决定种植一排共n棵树，只种植橡树和冷杉。他们制定了一个计划，可以用一个长度为n的二进制字符串s来表示。如果si=0，则第i棵树应该是橡树；如果si=1，则第i棵树应该是冷杉。

种植树木的前一天，学校的检查员将会来访。检查员非常热爱自然，他会按照以下方式评估树排的美丽程度：
- 首先，他会计算l0为连续的橡树的最大数量（在计划s中由零组成的最大子串）。如果一排没有橡树，则l0=0。
- 然后，他会计算l1为连续的冷杉的最大数量（在计划s中由一组成的最大子串）。如果一排没有冷杉，则l1=0。
- 最后，他会计算树排的美丽程度为a⋅l0+l1，其中a是检查员最喜欢的数字。

老师们知道参数a的值，但出于安全原因，他们不能告诉你。他们只告诉了你a是一个从1到n的整数。

由于树木尚未种植，老师们决定改变不超过k棵树的种类（即在计划中改变si从0到1或从1到0），以最大化根据检查员的评估，树排的美丽程度。

对于每个整数j从1到n，独立回答以下问题：
- 如果检查员最喜欢的数字a等于j，那么老师们通过改变不超过k棵树的类型，能实现的树排的最大美丽程度是多少？

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。
- 每个测试用例的第一行包含两个整数n和k（1≤n≤3000，0≤k≤n）——树排中的树木数量和最大变化数量。
- 第二行包含一个长度为n的由零和一组成的字符串s——计划描述。
- 保证所有测试用例的n值总和不超过3000。

输出：
- 对于每个测试用例，打印n个整数，其中第j个整数（1≤j≤n）是当a=j时，不超过k次改变后树排的最大美丽程度。

示例：
输入：
```
5
3 0
111
4 1
0110
5 0
10000
6 2
101101
7 1
0001101
```
输出：
```
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
```题目大意： 夏季信息学学校的老师们决定种植一排共n棵树，只种植橡树和冷杉。他们制定了一个计划，可以用一个长度为n的二进制字符串s来表示。如果si=0，则第i棵树应该是橡树；如果si=1，则第i棵树应该是冷杉。 种植树木的前一天，学校的检查员将会来访。检查员非常热爱自然，他会按照以下方式评估树排的美丽程度： - 首先，他会计算l0为连续的橡树的最大数量（在计划s中由零组成的最大子串）。如果一排没有橡树，则l0=0。 - 然后，他会计算l1为连续的冷杉的最大数量（在计划s中由一组成的最大子串）。如果一排没有冷杉，则l1=0。 - 最后，他会计算树排的美丽程度为a⋅l0+l1，其中a是检查员最喜欢的数字。 老师们知道参数a的值，但出于安全原因，他们不能告诉你。他们只告诉了你a是一个从1到n的整数。 由于树木尚未种植，老师们决定改变不超过k棵树的种类（即在计划中改变si从0到1或从1到0），以最大化根据检查员的评估，树排的美丽程度。 对于每个整数j从1到n，独立回答以下问题： - 如果检查员最喜欢的数字a等于j，那么老师们通过改变不超过k棵树的类型，能实现的树排的最大美丽程度是多少？ 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤1000）——测试用例的数量。 - 每个测试用例的第一行包含两个整数n和k（1≤n≤3000，0≤k≤n）——树排中的树木数量和最大变化数量。 - 第二行包含一个长度为n的由零和一组成的字符串s——计划描述。 - 保证所有测试用例的n值总和不超过3000。 输出： - 对于每个测试用例，打印n个整数，其中第j个整数（1≤j≤n）是当a=j时，不超过k次改变后树排的最大美丽程度。 示例： 输入： ``` 5 3 0 111 4 1 0110 5 0 10000 6 2 101101 7 1 0001101 ``` 输出： ``` 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 ```