가까운 문자열

오늘 문자열론 수업에서 모리스 교수는 두 문자열 사이의 거리를 구하는 여러 방법을 학생들에게 설명했다. 그중 한 방법은 다음과 같다. 길이가 $n$이고 십진수 숫자로만 이루어진 두 문자열 $s$와 $t$가 있다. 모리스 교수는 같은 위치에 있는 숫자 차이의 절댓값을 모두 더한 값을 두 문자열의 숫자 거리라고 부른다. 즉 $\sum_{i=1}^{n} |s_i - t_i|$이며, 여기서 $s_i$는 $s$의 $i$번째 위치에 적힌 숫자이고 $t_i$는 $t$의 $i$번째 위치에 적힌 숫자이다.

숙제로 교수는 학생마다 길이 $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$개로 이루어진 문자열이 주어진다.

목록의 $k$번째에 적힌, 길이 $n$의 십진수 숫자 문자열을 출력한다.

두 번째 예제에서 목록의 처음 일곱 단어는 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$이다. 즉 처음으로 다른 위치에서 첫 단어의 글자가 더 작다.