Tecle & Some

스트라이크 보이는 별명처럼 온갖 컴퓨터 게임에 푹 빠진 소년이다. 그는 컴퓨터를 쓸 수 없는 낙원 같은 섬에서 방학을 보내고 있다. 한동안은 휴대폰 게임으로 시간을 보냈지만 배터리가 다 떨어졌고 섬에는 전기가 없어서 더는 게임을 할 수 없었다. 그래서 스트라이크 보이는 휴대폰 키패드로 하는 새 놀이를 만들었다. 두 사람이 하는 이 놀이에서 한 사람이 두 정수 $S$와 $D$를 고르면, 상대는 다음 조건을 모두 만족하는 항의 수열을 찾아야 한다.

• 수열의 각 항은 $D$자리 십진수이다. 단, 마지막 항은 $1$자리 이상 $D$자리 이하이다.
• 수열의 모든 항의 합은 $S$이다.
• 항을 이루는 숫자는 휴대폰 표준 키패드의 키('0'부터 '9')에 해당한다.
• 각 숫자는 수열 전체에서 최대 한 번 쓰인다.
• 첫 항은 어떤 숫자로 시작해도 되지만, 수열의 숫자를 왼쪽에서 오른쪽으로 읽을 때 다음 키는 항상 바로 앞에 쓴 키와 세로, 가로 또는 대각선으로 바로 이웃한 키여야 한다. 항의 경계를 넘어갈 때도 마찬가지이다.

키패드의 배치는 다음과 같다. 0은 8의 바로 아래에 있으므로 0과 이웃한 키는 7, 8, 9이다.

1 2 3
4 5 6
7 8 9
  0

항은 쓰인 숫자를 그대로 나열한 문자열로 적는다. 따라서 어떤 항이든 0으로 시작할 수 있고(예: 074), 마지막 항도 0으로 시작할 수 있다(예: $D = 2$일 때 마지막 항 07).

예를 들어 $S = 230$, $D = 3$이면 규칙을 만족하는 해는 [074, 156]과 [085, 142, 3] 두 가지뿐이다. 수열 [230]은 키 '3'이 키 '0'과 이웃하지 않으므로 해가 아니다.

상대의 답이 맞는지 확인할 수 있도록 스트라이크 보이를 도와주자. $S$와 $D$가 주어질 때 가능한 모든 해를 출력하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로, 원하는 합 $S$와 각 항의 자릿수 $D$가 공백 하나를 사이에 두고 주어진다. ($0 \le S \le 10\,000\,000\,000$, $1 \le D \le 10$)

입력의 끝은 $S = D = -1$인 줄로 표시한다. 이 줄은 처리하지 않는다.

각 테스트 케이스마다 답을 출력한다. 답의 첫 줄에는 테스트 케이스 번호를 #i 형식으로 출력한다. i는 1부터 시작해서 테스트 케이스마다 1씩 증가한다.

해가 있으면 가능한 수열을 모두 한 줄에 하나씩 출력한다. 한 수열의 항은 공백 하나로 구분하고, 각 항은 앞에 붙은 0까지 포함해서 쓰인 숫자 그대로 출력한다. 해가 없으면 impossivel 한 단어만 한 줄에 출력한다.

수열은 사전순으로 증가하는 순서로 출력한다. 수열 $S_a = a_1 a_2 \ldots a_m$이 수열 $S_b = b_1 b_2 \ldots b_n$보다 앞선다는 것은 $S_b$가 비어 있지 않고 다음 중 하나가 성립한다는 뜻이다.

• $S_a$가 빈 수열이다.
• $a_1 < b_1$이다.
• $a_1 = b_1$이고 수열 $a_2 a_3 \ldots a_m$이 수열 $b_2 b_3 \ldots b_n$보다 앞선다.

여기서 두 항 $a_1$, $b_1$은 수의 값이 아니라 숫자 문자열로 비교한다. 즉 앞에서부터 한 글자씩 비교하고, 한 문자열이 다른 문자열의 접두사이면 짧은 쪽이 앞선다. 예를 들어 항 08은 항 8보다 앞서고, 항 012는 항 3보다 앞선다. 이 순서는 각 수열의 항을 공백 없이 이어 붙인 숫자 문자열을 같은 방식으로 비교한 순서와 같다.