Not So Distant Strings

Today in the string theory lecture, Professor Morris taught the students several ways to measure the distance between two strings. One of them works as follows. Let $s$ and $t$ be two strings of length $n$ made only of decimal digits. Professor Morris calls the digit distance between them the sum of absolute differences of the digits at equal positions, that is $\sum_{i=1}^{n} |s_i - t_i|$, where $s_i$ is the digit at position $i$ in $s$ and $t_i$ is the digit at position $i$ in $t$.

For homework, the professor gave each student a string of length $n$ and asked them to write out all strings of length $n$ (there are $10^n$ of them) in non-decreasing order of digit distance to that string. When two strings have the same distance, they are compared lexicographically.

The professor has little time to check each student's work, so he also gave each student a number $k$ and asks only for the string in the $k$-th place of the list. The students do not want to do this long and tedious task by hand, so they asked you to write a program that outputs the answer for a given string and number $k$.

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 200\,000$, $1 \leq k \leq \min(10^{n}, 10^{18})$), the length of the string given by the professor and the position $k$ in the final sequence that the professor is interested in.

The second line contains the string of $n$ decimal digits.

Print the string of $n$ decimal digits that is written in the $k$-th place of the sequence.

In the second example, the first seven words of the list are 00000, 00001, 00010, 00100, 01000, 10000, and 00002.

A word $x_1, x_2, \ldots, x_a$ is not greater than a word $y_1, y_2, \ldots, y_b$ in lexicographic order if one of the following two conditions holds:

• $a \leq b$ and $x_1 = y_1, \ldots, x_a = y_a$, so the first word is a prefix of the second.
• There is a position $1 \leq j \leq \min(a, b)$ such that $x_1 = y_1, \ldots, x_{j-1} = y_{j-1}$ and $x_j < y_j$. In other words, at the first position where the words differ, the letter in the first word is smaller.