소들이 알파벳 퍼즐을 시작했습니다. $R$행($(1 \le R \le 10)$), $C$열($(1 \le C \le 10)$)이며 모서리는 이상한 종이 모양 대신 문자입니다.

조각마다 번호와 $4$개 문자 또는 테두리가 있으며 보통 퍼즐처럼 맞춥니다. 가짜 문자 0(숫자 영)은 테두리입니다. 코너 조각이나 $4\times1$ 퍼즐 한 열의 맨 위 조각처럼 여러 테두리를 가질 수 있습니다. 아래 여섯 조각은 여러 해 중 하나이며 테두리는 0 대신 선입니다.

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

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

서로 접한 변의 문자가 같고 테두리는 위, 아래, 양쪽에 올바르게 있습니다.

번호와 시계 방향 네 변으로 조각을 표현하며 변은 $a,\ldots,z$ 문자 또는 0입니다. 놓을 때 회전이 필요할 수 있습니다.

적어도 한 조립 방법을 찾으세요. $R$와 $C$가 큰 테스트는 변의 문자가 다양해 더 쉽습니다.

입력

• $1$번 줄: 공백으로 구분된 정수 $R$와 $C$.

• $2,\ldots,R\times C+1$번 줄: 공백으로 구분된 다섯 항목, 정수 번호와 네 변 식별자.

출력

• $1,\ldots,R\times C$번 줄: $R\times (i-1)+j$번 줄은 $i$행 $j$열 조각을 다섯 항목으로 설명합니다. 정수 번호 다음 위, 오른쪽, 아래, 왼쪽 변 식별자입니다.

예제

입력 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

출력 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

참고

입력은 퍼즐을 설명하지만 일부 조각은 예제 해에 비해 회전되어 있습니다.

본문 그림과 같습니다. 대칭 등 다른 해도 가능하며 검사 프로그램이 확인합니다.

문제 출제자: Rob Kolstad, 2008