Erasing and Winning

Interview

Time limit2sMemory limit512 MB

Summary

Given an N-digit number and D, erase exactly D digits so the remaining digits, in order, form the largest possible number. Multiple test cases until 0 0.

Level: Medium5 of 10
Topics: Greedy, Stack, String, Implementation
Solved: No attempts yet

Problem

Juliano is a fan of the audience game show Erasing and Winning. The show picks its contestants by a draw and pays them prize money.

The show works like this. The host writes an $N$ -digit number on a board, and the contestant erases exactly $D$ of its digits. The digits that are left, read in their original order, form the number the contestant wins.

Juliano was finally picked as a contestant. Given the number the host wrote on the board and how many digits Juliano has to erase, write a program that finds the largest prize Juliano can win.

Input

The input contains several test cases. The first line of each test case has two integers $N$ and $D$ ( $1 \le D < N \le 10^5$ ), where $N$ is the number of digits of the number the host wrote and $D$ is how many digits must be erased. The next line has the number the host wrote. That number has no leading zeros.

The last line of the input has two zeros separated by a space. That line is not a test case.

Output

For each test case, print on one line the largest prize Juliano can win.

Examples2

Example 1

Input

Expected output

79
323
100

Example 2
Input
```
2 1
10
2 1
19
0 0
```
Expected output
```
1
9
```