Les vaches font des puzzles alphabétiques. Ils ont $R$ lignes ($(1 \le R \le 10)$) et $C$ colonnes ($(1 \le C \le 10)$), avec des lettres sur les bords plutôt que des formes de carton étranges.

Chaque pièce a un numéro et $4$ lettres ou bordures à aligner. La pseudo-lettre 0 (chiffre zéro) représente une bordure. Une pièce peut en avoir plusieurs, à un coin ou même en haut d'une colonne d'un puzzle $4\times1$. Les six pièces ci-dessous forment une solution parmi plusieurs ; les bordures sont des traits plutôt que 0.

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

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

Les lettres des bords adjacents correspondent et les bordures se trouvent correctement en haut, en bas et sur les côtés.

Chaque pièce est un numéro puis quatre bords dans le sens horaire, lettres $a,\ldots,z$ ou 0. Une rotation peut être nécessaire.

Trouvez au moins un assemblage. Les tests avec $R$ et $C$ plus grands sont plus faciles grâce à des lettres plus variées.

Entrée

• Ligne $1$ : entiers $R$ et $C$ séparés par un espace.

• Lignes $2,\ldots,R\times C+1$ : cinq éléments séparés par des espaces, numéro entier et quatre identifiants de bords.

Sortie

• Lignes $1,\ldots,R\times C$ : la ligne $R\times (i-1)+j$ décrit la pièce ligne $i$, colonne $j$ par cinq éléments séparés : numéro entier puis bords haut, droite, bas, gauche.

Exemples

Entrée 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

Sortie 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

Remarque

L'entrée décrit le puzzle avec certaines pièces tournées par rapport à la solution donnée.

Comme dans le schéma. D'autres solutions, telles les réflexions, sont possibles ; un programme vérifiera la réponse.

Auteur du problème : Rob Kolstad, 2008