C. Get the Long Binary Number
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a binary number $$$x$$$.Define $$$c0(x)$$$ as the number of $$$0$$$ in $$$x$$$,$$$c1(x)$$$ as the number of $$$1$$$ in $$$x$$$.

For example,$$$x=10100$$$,we can get $$$c0(x)=3,c1(x)=2$$$.

Now you're given a binary number $$$y$$$(without leading zero) of length $$$n$$$ and an integer $$$k$$$.Your task is find the smallest binary number $$$x$$$(without leading zero),which satisfies:

  1. $$$y \leq x$$$;
  2. $$$c0(x)-c1(x)=k$$$.
Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists of two line of input.

The first line contains two integers $$$n,k(1 \leq n \leq 10^5,-10^5 \leq k \leq 10^5)$$$.

The second line contains a binary number $$$y$$$(without leading zero) of length $$$n$$$.

The sum of $$$n,|k|$$$ over all test cases will not exceed $$$4*10^5$$$.

Output

For each test case,output on a new line — the smallest binary number $$$x$$$(without leading zero),which satisfies:

  1. $$$y \leq x$$$;
  2. $$$c0(x)-c1(x)=k$$$.
Example
Input
5
1 -1
0
6 -4
110100
6 1
100000
7 1
1110000
10 -2
1011010111
Output
1
110111
1000011
1110000
1011011001