На кафедре пингвиноведения Южного Антарктического университета проводятся исследования популяций пингвинов. Фотографии скоплений плотно стоящих пингвинов обрабатываются студентами. Распознавание пингвинов на снимках производится следующим образом: на фотографии выбирается характерная полоса высотой в один пиксель, каждый пиксель которой входит в изображение одного из пингвинов.
У всех пингвинов исследуемой популяции живот белый, а спина и крылья — чёрные. Таким образом, если у пингвина на фотографии видна только спина, то на характерной полосе ему соответствует отрезок из чёрных пикселей, а если только живот, то из белых. В остальных случаях, например, когда чёрные крылья видны поверх белого живота, пингвину соответствует отрезок из чёрных и белых пикселей. Для продолжения исследований необходимо, чтобы каждому пингвину соответствовал отрезок, состоящий либо только из чёрных, либо только из белых пикселей.
Для \(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\)-й фотографии. Если оптимальных упрощённых полос несколько, выведите любую из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
9 3
000111000
10 3
0111011010
4 4
0001
|
000111000
0111111000
0001
|