As vacas fazem quebra-cabeças alfabéticos com $R$ linhas ($(1 \le R \le 10)$) e $C$ colunas ($(1 \le C \le 10)$). As bordas são letras, não formas estranhas de papelão.

Cada peça tem número e $4$ letras ou bordas externas que se alinham. A pseudoletra 0 (dígito zero) é borda externa. Uma peça pode ter várias num canto ou mesmo no topo de uma coluna de um puzzle $4\times1$. As seis peças abaixo formam uma solução entre muitas; linhas indicam bordas em vez de 0.

              +---+  +---+  +---+
              | 1 c  c 3 d  d 5 |
              +-d-+  + a +  +-e-+

              +-d-+  +-a-+  +-e-+
              | 2 b  b 4 b  b 6 |
              +---+  +---+  +---+

As letras de lados adjacentes coincidem, e as bordas ficam corretamente no topo, embaixo e nos lados.

Cada peça tem número e quatro lados no sentido horário, letras $a,\ldots,z$ ou 0. Pode exigir rotação.

Encontre pelo menos uma montagem. Casos com $R$ e $C$ maiores são mais fáceis pela variedade de letras.

Entrada

• Linha $1$: inteiros $R$ e $C$ separados por espaços.

• Linhas $2,\ldots,R\times C+1$: cinco itens separados por espaços, número inteiro e quatro identificadores de lados.

Saída

• Linhas $1,\ldots,R\times C$: a linha $R\times (i-1)+j$ descreve a peça na linha $i$, coluna $j$, em cinco itens: número inteiro e lados cima, direita, baixo, esquerda.

Exemplos

Entrada 1

2 3
1 c d 0 0
2 0 d b 0
3 c 0 d a
4 b a b 0
5 d 0 0 e
6 0 0 b e

Saída 1

1 0 c d 0
3 0 d a c
5 0 0 e d
2 d b 0 0
4 a b 0 b
6 e 0 0 b

Note

A entrada descreve o puzzle, com algumas peças giradas em relação à solução de exemplo.

Como no diagrama. Outras soluções, como reflexões, são possíveis; um programa verifica a resposta.

Autor do problema: Rob Kolstad, 2008