题目描述

译自 ROI 2015 Day1 T4. Пингвиноведение

南极大学的企鹅研究系正在进行企鹅种群的研究。学生们负责处理密集站立企鹅群的照片。照片上企鹅的识别过程如下：在照片上选择一条高度为一个像素的「特征条带」，条带上的每个像素都属于某个企鹅的图像。

研究中的企鹅种群腹部为白色，背部和翅膀为黑色。因此，如果照片上只看到企鹅的背部，则特征条带上对应的是一段黑色像素；如果只看到腹部，则是一段白色像素。在其他情况下，例如黑色翅膀覆盖在白色腹部上时，企鹅对应的条带会包含黑色和白色像素。为了继续研究，需要确保每个企鹅对应的条带要么全为黑色像素，要么全为白色像素。

对于第 $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$ 张照片的特征条带得到的简化条带。如果存在多个最优简化条带，输出其中任意一个即可。

3
9 3
000111000
10 3
0111011010
4 4
0001

000111000
0111111000
0001

数据范围与提示

详细子任务附加限制及分值如下表所示：