Maximize Numeric String by Digit Replacement

You are given a non-negative integer k and a string s consisting of digits. You are allowed to replace at most k digits in s with the digit '9' to maximize the numeric value of the resulting string.

The task is to process the string from left to right and, whenever possible, change a digit (if it is not '9') to '9' until you have performed at most k replacements.

Formally, let \( s = s_1s_2\dots s_n \) and let \( k \) be the maximum number of replacements allowed. For each index \( i \) from 1 to \( n \), if \( s_i \neq 9 \) and you still have replacements left, replace \( s_i \) by 9. The final string is then printed as output.

Note: The operation should be performed in a greedy manner, modifying the leftmost digits first.

inputFormat

The input is provided via standard input (stdin) and consists of two lines:

1. The first line contains an integer \( k \) (the maximum number of digit replacements allowed).
2. The second line contains a string \( s \) representing a number.

It is guaranteed that \( s \) consists only of digits.

outputFormat

Output a single line via standard output (stdout) which is the maximum value string obtained after at most \( k \) replacements.

1
123456

923456