Las vacas hacen rompecabezas alfabéticos de $R$ filas ($(1 \le R \le 10)$) y $C$ columnas ($(1 \le C \le 10)$). Sus bordes son letras, en vez de formas extrañas de cartón.

Cada pieza tiene número y $4$ letras o bordes exteriores que deben alinearse. La pseudoletra 0 (dígito cero) representa borde exterior. Puede haber varios en una esquina o incluso arriba de una columna de un puzzle $4\times1$. Las seis piezas siguientes forman una solución entre muchas; líneas indican los bordes en vez de 0.

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

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

Las letras de los lados adyacentes coinciden y los bordes exteriores quedan arriba, abajo y a los lados.

Cada pieza tiene número y cuatro lados en sentido horario, letras $a,\ldots,z$ o 0. Puede necesitar rotación.

Encuentra al menos un ensamblaje. Los casos con $R$ y $C$ mayores son más fáciles por la variedad de letras.

Entrada

• Línea $1$: enteros $R$ y $C$ separados por espacios.

• Líneas $2,\ldots,R\times C+1$: cinco elementos separados por espacios, número entero y cuatro identificadores de lados.

Salida

• Líneas $1,\ldots,R\times C$: la línea $R\times (i-1)+j$ describe la pieza en fila $i$, columna $j$: cinco elementos separados, número entero y lados arriba, derecha, abajo, izquierda.

Ejemplos

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

Salida 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

Nota

La entrada describe el puzzle, con algunas piezas rotadas respecto a la solución de ejemplo.

Como en el diagrama. Otras soluciones, como reflejos, son posibles; un programa verifica la respuesta.

Autor del problema: Rob Kolstad, 2008