CF1256D.Binary String Minimizing

You are given a binary string of length $n$ (i. e. a string consisting of $n$ characters '0' and '1').

In one move you can swap two adjacent characters of the string. What is the lexicographically minimum possible string you can obtain from the given one if you can perform no more than $k$ moves? It is possible that you do not perform any moves at all.

Note that you can swap the same pair of adjacent characters with indices $i$ and $i+1$ arbitrary (possibly, zero) number of times. Each such swap is considered a separate move.

You have to answer $q$ independent test cases.

给你一个长度为 $n$ 的二进制字符串（即由 $n$ 个字符 '0' 和 '1' 组成的字符串）。

每次操作，你可以交换字符串中两个相邻的字符。如果最多执行 $k$ 次操作，你能从给定字符串得到的字典序最小的字符串是什么？你也可以完全不执行任何操作。

注意：你可以任意（可能为零）次地交换同一对相邻字符（下标为 $i$ 和 $i+1$ 的字符）。每一次这样的交换均视为一次独立的操作。

你需要回答 $q$ 个相互独立的测试用例。

The first line of the input contains one integer $q$ ($1 \le q \le 10^4$) — the number of test cases.

The first line of the test case contains two integers $n$ and $k$ ($1 \le n \le 10^6, 1 \le k \le n^2$) — the length of the string and the number of moves you can perform.

The second line of the test case contains one string consisting of $n$ characters '0' and '1'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ ($\sum n \le 10^6$).

输入的第一行包含一个整数 $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$）。

For each test case, print the answer on it: the lexicographically minimum possible string of length $n$ you can obtain from the given one if you can perform no more than $k$ moves.

对于每个测试用例，在一行中输出答案：即在最多执行 $k$ 次操作的前提下，从给定字符串所能得到的长度为 $n$ 的字典序最小的字符串。

In the first example, you can change the string as follows: $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$.

In the third example, there are enough operations to make the string sorted.

在第一个例子中，你可以按如下方式改变字符串：$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$。

在第三个例子中，操作次数足够使字符串变为有序。