bee 1484 - Type & Add

Strike Boy, as the name suggests, is a boy fanatic for all types of computer games. He is going on vacation in a paradise island where computers are not allowed. He had a great time playing with games on his cell phone, but now the battery is dead and since there is no electricity on the island, he stopped playing. Strike Boy then decided to invent a new hobby, using the keypad of his cell phone. In this new game, for two players, one chooses two integers S and D. The opposing player must then find a sequence of terms such that:

Each term of the sequence is a number with D decimal digits, except for the last term, which can have between 1 and D digits;
The sum of all terms of the sequence is equal to S ;
The digits used to form a term correspond to the keys of a standard cell phone keyboard ('0 'to '9');
Each digit is used at most once in the sequence;
The first term of a sequence can begin with any digit, but the order of the digits of the sequence when read from left to right, is such that the next key always corresponds to a key that is immediately adjacent to the previously used key (vertically, horizontally or diagonally).

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

Left picture: Keyboard illustrating the keys used to form the sequence [074, 156]

Right picture: Keyboard illustrating the keys used to form the sequence [085, 142, 3]

Help Strike Boy to check if his oponnent's answers are correct: write a program that, given S and D , print all possible solutions .

Input

The input contains several test cases. Each test consist in just one line, containing two integers S and D, separated by an empty space, representing the desired sum and the number of digits of each term (0 ≤ S ≤ 10.000.000.000 and 1 ≤ D ≤ 10). The end of the input is specified by S = D = −1.

Output

For each test case, your program must write one answer. The first line of an answer must contain an identifier of the test case, in the format '#i', where 'i' is initially 1 and is incremented for each test case. Then, if a solution for the problem exists, your program must display the list of the possible sequences of terms. If more than one sequence is possible, they must appear in ascending lexicographic order. Each sequence of terms must be printed in one line, with its terms separated by an empty space. If there is no solution, your program must print one line containing the word 'impossible'.

Definition: consider the sequences Sa = a₁a₂... a_m and S_b = b₁b₂ ... b_n. S_a preceeds S_b lexicographically if and only if S_b is non-empty and one of the following conditions is true:

S_a is an empty sequence;
a₁ < b₁;
a₁ = b₁ and the sequence a₂a₃ ... a_m preceeds sequence b₂b₃ ... b_n.

Sample Input	Sample Output
7 1 10 2 230 3 6311 4 2 2 -1 -1	#1 0 7 1 2 4 1 4 2 2 1 4 2 4 1 2 5 4 1 2 4 2 1 5 2 7 7 0 #2 impossible #3 074 156 085 142 3 #4 0896 5412 3 0986 5321 4 0986 5324 1 0987 5324 #5 2