Недалёкие строки

Сегодня на уроке строковедения профессор Моррис рассказывал студентам различные способы вычисления расстояния между двумя строками. Один из способов был следующий, пусть имеются две строки $s$ и $t$ длины $n$, состоящие только из десятичных цифр. Тогда цифровым расстоянием между двумя данными строками профессор Моррис считает сумму модулей разности цифр на одинаковых позициях, то есть $\sum\_{i = 1}^{n} |s\_i - t\_i|$, где $s\_i$ означает цифру, записанную на позиции $i$ в строке $s$, а $t\_i$ означает цифру, записанную на позиции $i$ в строке $t$.

В качестве домашнего задания профессор дал каждому студенту строку длины $n$ и поручил выписать все строки длины $n$ (а это целых $10^n$ строк) в порядке неубывания цифрового расстояния до данной строки. При равенстве расстояния до двух строк, их следует сравнивать лексикографически.

Поскольку у профессора мало времени, чтобы проконтролировать выполнение всего задания каждым из студентов, он дополнительно сообщил каждому из них число $k$ и просит лишь сказать ему строку, находящуюся на $k$-м месте в выписанной последовательности. Студенты не горят желанием выполнять вручную столь объёмное и монотонное задание, поэтому попросили вас написать программу, которая будет выводить ответ по заданной строке и числу $k$.

В первой строке входных данных записаны два целых числа $n$ и $k$ ($1 \leq n \leq 200\\,000$, $1 \leq k \leq \min(10^{n}, 10^{18})$) --- длина строки, выданной профессором, и интересующая профессора позиция в итоговой последовательности.

Во второй строке записана строка, состоящая из $n$ десятичных цифр.

Выведите строку из $n$ десятичных цифр, которая будет записана на $k$-м месте в интересующей профессора последовательности.

Во втором примере первые семь слов списка это <<00000>>, <<00001>>, <<00010>>, <<00100>>, <<01000>>, <<10000>> и <<00002>>.

Слово $x\_1, x\_2, \ldots, x\_a$ не превосходит слова $y\_1, y\_2, \ldots, y\_b$ в лексикографическом порядке если верно одно из двух условий:

• либо $a \leq b$ и $x\_1 = y\_1, \ldots, x\_a = y\_a$, то есть первое слово является префиксом второго;
• либо есть такая позиция $1 \leq j \leq \min(a, b)$, что $x\_1 = y\_1, \ldots, x\_{j-1} = y\_{j-1}$ и $x\_j < y\_j$, то есть, в первой позиции, в которой слова отличаются, в первом слове стоит меньшая буква.