Tecle & Some

Strike Boy, as his nickname suggests, is a boy obsessed with every kind of computer game. He is spending his vacation on a paradise island where computers are not allowed. He had fun for a while with the games on his cell phone, but the battery ran out and the island has no electricity, so he had to stop playing. Strike Boy then invented a new pastime that uses his phone's keypad. In this two-player game, one player chooses two integers $S$ and $D$. The opponent must then find a sequence of terms such that:

• Every term of the sequence is a number with $D$ decimal digits, except the last term, which may have between $1$ and $D$ digits.
• The sum of all terms of the sequence is $S$.
• The digits that form the terms correspond to the keys of a standard cell phone keypad ('0' to '9').
• Each digit is used at most once in the whole sequence.
• The first term may start with any digit, but when the digits of the sequence are read from left to right, each key is always an immediate neighbor of the previously used key (vertically, horizontally, or diagonally). This also holds across the boundary between two terms.

The keypad layout is shown below. The 0 key is directly below 8, so the neighbors of 0 are 7, 8, and 9.

1 2 3
4 5 6
7 8 9
  0

A term is written as the exact string of digits it uses. Any term may therefore start with 0 (for example 074), and so may the last term (for example, with $D = 2$, a last term 07).

For example, if $S = 230$ and $D = 3$, there are only two solutions that obey the rules: [074, 156] and [085, 142, 3]. The sequence [230] is not a solution because key '3' is not a neighbor of key '0'.

Help Strike Boy check whether his opponent's answers are correct: write a program that, given $S$ and $D$, prints every possible solution.

The input contains several test cases. Each test case is a single line with two integers $S$ and $D$ separated by one space: the desired sum and the number of digits of each term ($0 \le S \le 10\,000\,000\,000$, $1 \le D \le 10$).

The end of the input is marked by a line with $S = D = -1$. Do not process that line.

For each test case, print one answer. The first line of an answer is the test case identifier in the format #i, where i starts at 1 and increases by one for each test case.

If a solution exists, print every possible sequence, one per line. Separate the terms of a sequence with a single space, and print each term exactly as the digits it uses, including leading zeros. If there is no solution, print a line containing only the word impossivel.

Print the sequences in increasing lexicographic order. Sequence $S_a = a_1 a_2 \ldots a_m$ precedes sequence $S_b = b_1 b_2 \ldots b_n$ if and only if $S_b$ is non-empty and one of the following holds:

• $S_a$ is the empty sequence.
• $a_1 < b_1$.
• $a_1 = b_1$ and the sequence $a_2 a_3 \ldots a_m$ precedes the sequence $b_2 b_3 \ldots b_n$.

Here two terms $a_1$ and $b_1$ are compared as digit strings, not as numeric values: character by character from the left, and if one string is a prefix of the other, the shorter one comes first. For example, the term 08 precedes the term 8, and the term 012 precedes the term 3. This order is the same as comparing, in the same way, the digit strings obtained by concatenating the terms of each sequence without spaces.