SPOJ Brasil

Strike Boy, como o apelido sugere, é um garoto fanático por todo tipo de jogos em computador. Ele está passando as férias em uma ilha paradisíaca, onde computadores não são permitidos. Ele se divertiu por algum tempo com os jogos em seu telefone celular, mas a bateria acabou e não há eletricidade na ilha, de forma que ele parou de jogar. Strike Boy então decidiu inventar um novo passatempo, usando o teclado de seu telefone celular. Neste novo jogo, para dois jogadores, um deles escolhe dois inteiros S e D. O jogador oponente deve então encontrar uma seqüência de termos tal que:

• cada termo da seqüência é um número com D dígitos decimais, exceto pelo ultimo termo, que pode ter entre 1 e D dígitos;

• a soma de todos os termos da seqüência é igual a S;

• os dígitos utilizados para formar um termo correspondem às teclas de um teclado padrão de telefone celular (‘0’ a ‘9’);

• cada dígito é utilizado no máximo uma vez na seqüência;

• o primeiro termo de uma seqüência pode começar com qualquer dígito, mas a ordem dos dígitos da seqüência, quando lidos da esquerda para a direita, é tal que a próxima tecla corresponde sempre a uma tecla imediatamente vizinha da tecla utilizada previamente (na vertical, na horizontal ou na diagonal).

Por exemplo, se S = 230 e D = 3, há apenas duas soluções possíveis obedecendo as regras do jogo: [074, 156] e [085, 142, 3]. A seqüência [230] não é uma solução porque a tecla ‘3’ não é vizinha da tecla ‘0’.

Ajude Strike Boy a verificar se as respostas do oponente estão corretas: escreva um programa que, dados S e D, imprima todas as soluções possíveis.

Entrada

A entrada contém vários casos de teste. Cada caso de teste consiste em apenas uma linha, contendo dois inteiros S e D, separados por um espaço, representando a soma desejada e o número de dígitos de cada termo (0 <= S <= 10.000.000.000 e 1 <= D <= 10). O final da entrada é indicado por S = D = −1.

Saída

Para cada caso de teste da entrada seu programa deve produzir uma resposta. A primeira linha de uma resposta deve conter um identificador do caso de teste, no formato ‘#i’, onde ‘i’ tem inicialmente o valor 1 e é incrementado a cada caso de teste. Então, se uma solução para o passatempo existe, seu programa deve produzir uma lista das possíveis seqüências de termos. Se mais de uma seqüência é possível, elas devem aparecer em ordem lexicográfica crescente. Cada seqüência de termos deve ser impressa em uma linha, com os termos separados por um espaço em branco. Se não há solução, seu programa deve imprimir uma linha contendo a palavra ‘impossivel’ (note ausência de acentuação).

Definição: considere as seqüências S_a = a₁ a₂ ...a_m e S_b = b₁ b₂ . . . b_n. S_a precede S_b em ordem lexicográfica se e apenas se S_b é não-vazia e uma das seguintes condições é verdadeira:

• S_a é uma seqüência vazia;

• a₁ < b₁; • a₁ = b₁ e a seqüência a₂ a₃ . . . a_m precede a seqüência b₂ b₃ . . . b_n.

Exemplo de entrada

7 1
10 2
230 3
6311 4
2 2
-1 -1

Saída para o exemplo de entrada

#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
impossivel
#3
074 156
085 142 3
#4
0896 5412 3
0986 5321 4
0986 5324 1
0987 5324
#5
2