题目背景

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

题目描述

南极南部大学的企鹅学系正在进行企鹅种群的研究工作。研究人员将密集站立的企鹅群体进行拍照，随后由学生对这些照片进行处理。企鹅的识别方式如下：在照片上选取一条特征条带，该条带的高度为 1 个像素，并且条带上的每个像素都属于某一只企鹅的图像。

研究中的企鹅都有相似的体色特征：腹部为白色，背部和翅膀为黑色。因此：

• 若照片上只看到企鹅的背部，则对应的条带上会出现一段连续的黑色像素；
• 若只看到腹部，则为连续的白色像素；
• 若既能看到翅膀又能看到腹部（例如翅膀遮在白色腹部前），则该企鹅对应的条带上会出现由黑白混合组成的像素段。

为了便于后续研究，需要保证每只企鹅在特征条带上都对应一个仅由黑色或仅由白色像素组成的连续段。

对于第 $i$ 张照片，已知其特征条带上可能出现的企鹅数量不超过 $k_i$。因此，必须将该条带替换为一条长度相同的简化条带，它由不超过 $k_i$ 个连续的色段组成，每个色段要么全为黑色，要么全为白色。在所有可能的简化条带中，需要选择一种最优方案，即通过最少次数地修改像素颜色，使原条带转化为合法的简化条带。

请编写程序完成上述任务。

输入格式

输入的第一行包含整数 $t$ —— 照片的数量。接下来有 $t$ 组数据，每组对应一张照片。

每组数据的第一行包含两个整数：

• $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

提示

数据范围