← 返回题目列表

Codeforces · 1256/D

D. 二进制字符串最小化

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的二进制字符串(即由 $$$n$$$ 字符“0”和“1”组成的字符串)。

在一步操作中,您可以交换字符串中两个相邻的字符。如果您可以执行不超过 $$$k$$$ 的移动,那么从给定字符串中可以获得的按字典顺序排列的最小可能字符串是多少?您可能根本不执行任何动作。

请注意,您可以任意(可能为零)多次交换索引 $$$i$$$ 和 $$$i+1$$$ 的同一对相邻字符。每次此类交换都被视为单独的举动。

您必须回答 $$$q$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^4$$$) — 测试用例的数量。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^6, 1 \le k \le n^2$$$) — 字符串的长度和可以执行的移动次数。

测试用例的第二行包含一个由 $$$n$$$ 字符“0”和“1”组成的字符串。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$ ($$$\sum n \le 10^6$$$)。

输出

对于每个测试用例,在其上打印答案:如果您可以执行不超过 $$$k$$$ 的移动,则可以从给定的字符串中获得长度为 $$$n$$$ 的字典顺序最小可能字符串。

示例

输入 #1

3
8 5
11011010
7 9
1111100
7 11
1111100

输出 #1

01011110
0101111
0011111

注意

在第一个示例中,您可以按如下方式更改字符串: $$$1\underline{10}11010 \rightarrow \underline{10}111010 \rightarrow 0111\underline{10}10 \rightarrow 011\underline{10}110 \rightarrow 01\underline{10}1110 \rightarrow 01011110$$$。

在第三个示例中,有足够的操作来对字符串进行排序。