Krowy układają alfabetyczne puzzle o $R$ wierszach ($(1 \le R \le 10)$) i $C$ kolumnach ($(1 \le C \le 10)$). Krawędzie są literami zamiast dziwnych kształtów kartonu.

Każdy element ma numer i $4$ litery lub brzegi do dopasowania. Pseudolitera 0 (cyfra zero) oznacza brzeg. Może ich być kilka w narożniku albo na górze kolumny puzzli $4\times1$. Sześć elementów poniżej to jedno z wielu ułożeń; brzegi oznaczono liniami zamiast 0.

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

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

Litery stykających się krawędzi pasują, a brzegi są prawidłowo na górze, dole i bokach.

Element opisują numer i cztery krawędzie zgodnie z zegarem, litery $a,\ldots,z$ lub 0. Przy ułożeniu może wymagać obrotu.

Znajdź choć jedno ułożenie. Testy z większymi $R$ i $C$ są łatwiejsze dzięki różnorodniejszym literom.

Wejście

• Wiersz $1$: całkowite $R$ i $C$ oddzielone spacją.

• Wiersze $2,\ldots,R\times C+1$: pięć wartości oddzielonych spacjami, całkowity numer i cztery oznaczenia krawędzi.

Wyjście

• Wiersze $1,\ldots,R\times C$: wiersz $R\times (i-1)+j$ opisuje element w wierszu $i$, kolumnie $j$ pięcioma wartościami: całkowity numer i krawędzie góra, prawo, dół, lewo.

Przykład

Wejście 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

Wyjście 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

Uwagi

Wejście opisuje puzzle, lecz niektóre elementy obrócono względem przykładowego rozwiązania.

Jak na diagramie. Inne rozwiązania, np. odbicia, są możliwe; program sprawdza odpowiedź.

Autor zadania: Rob Kolstad, 2008