Die Kühe legen Buchstabenpuzzles mit $R$ Zeilen ($(1 \le R \le 10)$) und $C$ Spalten ($(1 \le C \le 10)$). Die Kanten sind Buchstaben statt seltsam geformter Pappe.

Jedes Teil hat eine Nummer und $4$ Buchstaben oder Ränder zum Zusammenpassen. Pseudobuchstabe 0 (Ziffer Null) bedeutet Rand. Ein Teil kann mehrere haben, etwa an einer Ecke oder oben in einer Spalte eines $4\times1$-Puzzles. Die sechs Teile unten zeigen eine von vielen Lösungen; Linien stehen für Ränder statt 0.

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

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

Buchstaben an anliegenden Kanten stimmen überein; Ränder liegen oben, unten und an den Seiten.

Ein Teil wird durch Nummer und vier Kanten im Uhrzeigersinn dargestellt, Buchstaben $a,\ldots,z$ oder 0. Beim Einsetzen kann Drehen nötig sein.

Finde mindestens eine Zusammensetzung. Größere $R$ und $C$ sind in Tests wegen vielfältigerer Buchstaben leichter.

Eingabe

• Zeile $1$: durch Leerzeichen getrennte ganze Zahlen $R$ und $C$.

• Zeilen $2,\ldots,R\times C+1$: fünf durch Leerzeichen getrennte Angaben, ganzzahlige Nummer und vier Kantenkennungen.

Ausgabe

• Zeilen $1,\ldots,R\times C$: Zeile $R\times (i-1)+j$ beschreibt das Teil in Zeile $i$, Spalte $j$ durch fünf Angaben: ganzzahlige Nummer und Kanten oben, rechts, unten, links.

Beispiele

Eingabe 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

Ausgabe 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

Hinweis

Die Eingabe beschreibt das Puzzle, einige Teile sind gegenüber der Beispiellösung gedreht.

Wie in der Zeichnung. Andere Lösungen, etwa Spiegelungen, sind möglich; ein Prüfprogramm kontrolliert die Antwort.

Aufgabenautor: Rob Kolstad, 2008