INS14C - Digo plays with Numbers


Digo and his friend Sharry have completed their missions and were relaxing. Both of them love mathematics and love to play with numbers. They have a book in which several binary strings are written. Digo comes up with an idea of an interesting game. He asks Sharry to think of a number K, which is less than or equal to the length of the string N. Both players play alternately. In his turn, a person can remove any bit from the binary string. Digo removes such as to maximize the value of the leftover binary string while Sharry plays to minimize the string. This process continues until K binary digits are left. You have to tell those K binary digits left after the game is over.

It is given that Sharry always plays first.

Input

The first line consists of a single integer T, denoting the number of test cases. 2 * T lines follow. For every test case, the first line consists of two integers N and K, denoting the initial length of the string and its length at the end of the game. The second line for the test case contains the initial binary string of length N.

Output

For each test case print the final string left after removal of characters.

Constraints

1 <= T <= 1000
1 <= N <= 1000
1 <= K <= N

Sample

Input:
2
5 3
10010
4 2
1111

Output:
010
11

hide comments
slothsphereoj: 2024-03-06 03:43:32

Some test cases fyr:

[Input]
4
6 4
110110
8 4
01101100
8 3
00110100
7 2
1110101

[Output]
1110
1100
000
11

nadstratosfer: 2017-09-26 06:45:49

dwij28: Just got AC with Python3 at less than half your PyPy time :P. It's exactly this kind of problems where optimizing Python code is fun, because you have to know what you're doing rather than have the compiler figure it out for you.

dwij28: 2016-08-26 23:02:30

Python 2.7 gets a TLE, PyPy gets an AC. I am too lazy to optimize or write ad-hoc string problems in C++.

rayhan50001: 2016-06-17 12:14:32

critical case:
input:
2
0 0
123456789
0 5
123456789
output:
123456789
123456789

samyak choudhary: 2015-06-24 16:22:26

" a person CAN remove any bit", wrongly worded question - that "can" should not be there, it costed me 2 wa.
Moreover, if the players had a choice to remove - as the "can" is supposed to indicate - then Digo will not remove any digit in his turn unless the leftover binary string is of the form 0**... (which is changed to **.. i.e. the initial 0 is removed). In case the left over string is devoid of any '1's and it's length is greater than k, the extra '0's will be removed.

However, since the question writer ended up adding an unnecessary modal - "can" - all this isn't required. -_-

darol: 2015-01-22 22:04:34

found it after few WA, missed that K can be Equal to N so the string printed is same as readed.

Last edit: 2015-01-22 22:34:58
bourne: 2014-09-12 09:51:25

Getting strange "Internal Error" ...any ideas why ? Thanks

Raghav Aggiwal: 2014-09-04 20:12:27

@surya kiran sir : can u plz tell me where i m going wrong <snip>

Last edit: 2022-09-17 23:32:40
abhishek arora: 2014-08-16 15:32:10

@Surya kiran.. pls help..getting wrong answer..( Submission id 12162332 )

Prajval Prabhakar: 2014-08-10 08:39:26

My 50th :)


Added by:Surya Kiran
Date:2014-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Insomnia 2014