D. Деревья и отрезки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Преподаватели ЛКШ решили посадить $$$n$$$ деревьев в ряд, причём было решено сажать только дубы и ели. Для этого они составили план, который можно представить в виде двоичной строки $$$s$$$ длины $$$n$$$. Если $$$s_i = 0$$$, то $$$i$$$-м деревом в ряду должен быть дуб, а если $$$s_i = 1$$$, то $$$i$$$-м деревом в ряду должна быть ель.

День посадки деревьев уже завтра, а послезавтра в ЛКШ приедет проверяющий. Проверяющий очень любит природу, и он оценит красоту ряда деревьев следующим образом:

  • Он вычислит $$$l_0$$$ как максимальное количество подряд идущих дубов в ряду (максимальная подстрока из нулей в плане $$$s$$$). Если в ряду нет дубов, то $$$l_0 = 0$$$.
  • Он вычислит $$$l_1$$$ как максимальное количество подряд идущих елей в ряду (максимальная подстрока из единиц в плане $$$s$$$). Если в ряду нет елей, то $$$l_1 = 0$$$.
  • Красота ряда деревьев будет равна $$$a \cdot l_0 + l_1$$$ для некоторого $$$a$$$ — любимого числа проверяющего.

Преподаватели знают значение параметра $$$a$$$, но не могут сказать его вам из соображений безопасности. Они готовы сказать вам лишь то, что $$$a$$$ является целым числом от $$$1$$$ до $$$n$$$.

Поскольку деревья ещё не посажены, преподаватели решили изменить вид не более чем $$$k$$$ деревьев на противоположный (то есть изменить $$$s_i$$$ с $$$0$$$ на $$$1$$$ или с $$$1$$$ на $$$0$$$ в плане), чтобы максимизировать красоту ряда деревьев по мнению проверяющего.

Для каждого целого $$$j$$$ от $$$1$$$ до $$$n$$$ найдите независимо ответ на следующий вопрос:

  • Какой максимальной красоты ряда деревьев могут добиться преподаватели, изменив вид не более чем $$$k$$$ деревьев, если любимое число проверяющего $$$a$$$ равно $$$j$$$?
Входные данные

В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 3000$$$, $$$0 \le k \le n$$$) — количество деревьев в ряду и максимальное количество изменений.

Вторая строка содержит строку $$$s$$$ длины $$$n$$$, состоящую из нулей и единиц — описание плана.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ чисел, $$$j$$$-е ($$$1 \le j \le n$$$) из которых — максимальная красота ряда деревьев после не более, чем $$$k$$$ изменений, если для вычисления красоты используется $$$a = j$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных не разрешаются изменения, поэтому всегда выполняется $$$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$$$ от $$$1$$$ до $$$4$$$.