Binary Number

Markyyz is learning binary numbers. There is an easy problem in his homework.

You are given a binary number $s_{1\sim n}$ ($s_1$ is the highest bit. $s_n$ is the lowest bit.). You need to do an operation exactly $k$ times: select an interval $[l,r]$ $(1\leq l \leq r \leq n)$ arbitrarily and flip $s_l,s_{l+1},...,s_{r}$, in other word, for all $i\in[l,r]$, $s_i$ becomes $1$ if $s_i$ is $0$, $s_i$ becomes $0$ if $s_i$ is $1$. What is the biggest result binary number after the $k$ operations.

Markyyz found useless algorithms useless on the problem, so he asked SPY for help. SPY looked down on the problem but finally got WA (wrong answer). Can you help them to find the right solution?

The first line of the input contains a single integer $T$ $(1\leq T \leq 6\times 10^4)$, indicating the number of test cases.

In each test case:

The first line contains two integers $n,k$. $(1\leq n\leq 10^5, 0\leq k\leq 10^{18})$

The second line contains a binary number $s_{1\sim n}$. $(s_1=1$, $\forall i\in[2,n]:s_i\in \{0,1\})$

It's guarenteed that in all test cases, $\sum n\leq 2.5\times 10^6$

You need to print a string of length $n$ in one line, representing the biggest binary number after the $k$ operations.

2
8 2
10100101
5 233333333333333333
11101

11111101
11111

2023“钉耙编程”中国大学生算法设计超级联赛（2）