21502번 - Пингвиноведение 서브태스크스페셜 저지다국어

На кафедре пингвиноведения Южного Антарктического университета проводятся исследования популяций пингвинов. Фотографии скоплений плотно стоящих пингвинов обрабатываются студентами. Распознавание пингвинов на снимках производится следующим образом: на фотографии выбирается характерная полоса высотой в один пиксель, каждый пиксель которой входит в изображение одного из пингвинов.

У всех пингвинов исследуемой популяции живот белый, а спина и крылья --- чёрные. Таким образом, если у пингвина на фотографии видна только спина, то на характерной полосе ему соответствует отрезок из чёрных пикселей, а если только живот, то из белых. В остальных случаях, например, когда чёрные крылья видны поверх белого живота, пингвину соответствует отрезок из чёрных и белых пикселей. Для продолжения исследований необходимо, чтобы каждому пингвину соответствовал отрезок, состоящий либо только из чёрных, либо только из белых пикселей.

Для $i$-й фотографии известно максимальное количество пингвинов $k_i$, изображение которых могло попасть на характерную полосу. Поэтому эту полосу пикселей необходимо заменить на упрощённую полосу той же длины, которая будет состоять не более чем из $k_i$ отрезков, каждый из которых либо полностью чёрный, либо полностью белый. Из всех возможных упрощённых полос нужно выбрать оптимальную --- то есть ту, которая получается из характерной путём изменения цвета минимального числа пикселей.

Требуется написать программу, решающую поставленную задачу.

В первой строке входных данных содержится число $t$ --- количество фотографий. Далее следуют $t$ пар строк, $i$-я пара строк описывает $i$-ю фотографию.

Первая строка описания фотографии содержит два числа: $n_i$ --- длину характерной полосы $i$-й фотографии, и $k_i$ --- максимальное количество пингвинов, которые могут быть на ней изображены ($k_i \le n_i$).

Вторая строка описания состоит из $n_i$ символов 0 и 1, где 0 обозначает чёрный, а 1 --- белый пиксель.

Выходные данные должны содержать $t$ строк, где $i$-я строка состоит из $n_i$ символов 0 и 1 и описывает упрощённую полосу, полученную из характерной полосы $i$-й фотографии. Если оптимальных упрощённых полос несколько, выведите любую из них.