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

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

hide comments
2014-06-09 07:10:49 drfgthyjuikjhgftrd
pls help getting wa:( <snip>

Last edit: 2022-09-17 23:32:35
2014-04-15 06:13:36 Beginner :P
Sample Input:
1
8 4
01101100
Sample Output:
1100
2014-04-01 15:36:16 NISHANT RAJ
Easy one...
2014-03-24 14:49:01 knb_dtu
What if there's no digit which can maximize the value of binary number?


Last edit: 2014-03-24 16:14:52
2014-03-26 22:30:39 MENDAX
is test case ??
Sample Input:
2
5 2
10010
4 2
1111
Sample Output:
010
11

Edit: Please read the problem carefully!

Last edit: 2014-03-26 22:31:01
2014-03-20 21:36:08 Jacob Plachta
N can be equal to K - the problem isn't clear about this.

Edit: Thanks for the update.

Last edit: 2014-03-21 00:35:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.