CF1858D Trees and Segments

夏季信息学学校的教师们决定在一排中种植 $ n $ 棵树，而且决定只种植橡树和冷杉树。为此，他们制定了一个计划，可以用长度为 $ n $ 的二进制字符串 $ s $ 表示。如果 $ s_i = 0 $，则第 $ i $ 棵树应该是橡树，如果 $ s_i = 1 $，则第 $ i $ 棵树应该是冷杉树。 树木种植的日子就是明天，后天一个督察将来到学校。督察非常喜欢大自然，他将根据以下方式评估这一排树的美丽程度： - 首先，他将计算 $ l_0 $，作为该计划 $ s $ 中连续的橡树的最大数目（计划 $ s $ 中由零构成的最大子串）。如果树行中没有橡树，则 $ l_0 = 0 $。 - 然后，他将计算 $ l_1 $，作为该计划 $ s $ 中连续的冷杉树的最大数目（计划 $ s $ 中由一构成的最大子串）。如果树行中没有冷杉树，则 $ l_1 = 0 $。 - 最后，他将计算树行的美丽程度为 $ a \cdot l_0 + l_1 $，其中 $ a $ 是督察最喜欢的数。 教师们知道参数 $ a $ 的值，但出于安全原因，他们不能告诉你。他们只告诉你 $ a $ 是从 $ 1 $ 到 $ n $ 的整数。 由于树木尚未种植，教师们决定在不超过 $ k $ 棵树上更改树的类型（即在计划中从 $ 0 $ 更改为 $ 1 $ 或从 $ 1 $ 更改为 $ 0 $），以便根据督察的计算来最大化树行的美丽程度。 对于从 $ 1 $ 到 $ n $ 的每个整数 $ j $ 独立回答以下问题： - 如果督察最喜欢的数为 $ j $，则在不超过 $ k $ 次更改的情况下，教师们可以通过更改树的类型来实现树行的最大美丽程度是多少？

第一行包含一个整数 $ t $（$ 1 \le t \le 1000 $） — 测试用例的数量。 每个测试用例由一行组成，包含两个整数 $ n $ 和 $ k $（$ 1 \le n \le 3000 $，$ 0 \le k \le n $） — 行中树木的数量以及最大更改次数。 第二行包含长度为 $ n $ 的字符串 $ s $，由零和一组成 — 计划的描述。 保证所有测试用例中的所有 $ n $ 值的总和不超过 $ 3000 $。

对于每个测试用例，输出 $ n $ 个整数，其中第 $ j $ 个整数（$ 1 \le j \le n $）是在使用 $ a = j $ 计算美丽程度后，教师们在不超过 $ k $ 次更改的情况下可以实现的树行的最大美丽程度。

在第一个测试用例中，不允许进行任何更改，因此始终满足 $ l_0 = 0 $ 和 $ l_1 = 3 $。因此，不管 $ a $ 的值如何，树行的美丽程度都将是 $ 3 $。 在第二个测试用例中，对于 $ a \in \{1, 2\} $，教师们可以将计划 $ s $ 更改为 $ 0111 $（通过更改 $ s_4 $），对于 $ a \in \{3, 4\} $，他们可以将计划 $ s $ 更改为 $ 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 $ 从 $ 1 $ 到 $ 4 $ 都是最优的。