Problem Description
Yu Peng the Penguin is taking photos with his penguin friends today! Penguins have white bellies and black wings
and back, and as penguins are more or less of the same height, the photos taken can be represented as a binary
string, where '0' denotes a black pixel and '1' denotes a white pixel.
Yu Peng has taken T photos, where the ith photo is of length Ni. He tells you
that in the ith photo, there are at most Ki penguins. Yu Peng recognises a penguin as
a contiguous segment of white pixels (penguin with belly facing front), or a contiguous segment of black pixels
(penguin with back facing front), both of arbitrary length. However, some naughty penguins faced the camera sideways when
the photos were taken, and hence, there may be more than Ki penguins in the ith photo,
according to Yu Peng's rules.
Yu Peng is not happy with these naughty penguins and wants to edit the photos. He wonders, for the ith
photo, what is the minimum number of pixels that he has to change the colour of, such that he sees at most
Ki penguins in the photo.
Input
The first line contains a single integer T, the number of photos.
Then, there are T pairs of lines, each describing a single photo taken.
For the ith pair of lines:
The first line contains two integers Ni and Ki.
The second line contains a binary string of length Ni.
Output
Output T lines. The ith line should contain a binary string of length Ni,
describing the ith edited photo, according to Yu Peng's requirements.
If there are several possible optimal edited photos, output any of them.
Limits
Subtask 1 (11%): 1 ≤ Ki ≤ Ni ≤ 10. 1 ≤ ∑ Ni ≤ 5000.
Subtask 2 (24%): 1 ≤ Ki ≤ Ni ≤ 100. 1 ≤ ∑ Ni ≤ 5000.
Subtask 3 (24%): 1 ≤ Ki ≤ Ni ≤ 1000. 1 ≤ ∑ Ni ≤ 50 000.
Subtask 4 (21%): 1 ≤ Ki ≤ 5000. 1 ≤ ∑ Ni ≤ 100 000.
Subtask 5 (20%): 1 ≤ Ki ≤ 200 000. 1 ≤ ∑ Ni ≤ 200 000.
Subtask 6 (0%): Sample Testcases
Sample Testcase 1
Input
3
9 3
000111000
10 3
0111011010
4 4
0001
Output
000111000
0111111000
0001