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

문제

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

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

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

입력

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

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

출력

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

힌트

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

Слово $x_1,x_2,\dots ,x_{a}x\_1,\; x\_2,\; \backslash ldots,\; x\_a$ не превосходит слова $y_1,y_2,\dots ,y_{b}y\_1,\; y\_2,\; \backslash ldots,\; y\_b$ в лексикографическом порядке если верно одно из двух условий:

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