조각 그림 퍼즐

소들이 알파벳 조각 그림 퍼즐을 맞추고 있다. 퍼즐은 $R$개의 행과 $C$개의 열로 이루어지며 ($1 \le R \le 10$, $1 \le C \le 10$), 조각들이 맞물리는 부분은 튀어나온 판지 모양이 아니라 각 변에 적힌 글자로 표현된다.

각 조각은 하나의 일련번호와 네 변의 정보로 주어진다. 한 변은 소문자(a–z)이거나 문자 0이다. 0은 조립된 직사각형의 바깥쪽에 놓이는 변, 즉 테두리를 뜻한다. 모서리 조각은 테두리 변이 두 개, 가장자리 조각은 한 개이며, (충분히 큰 퍼즐이라면) 내부 조각은 테두리 변이 없다.

퍼즐을 풀려면 모든 조각을 $R \times C$ 격자에 배치해서 다음을 만족해야 한다.

• 서로 맞닿은 두 조각의 접하는 변에는 같은 글자가 적혀 있어야 한다.
• 격자 바깥 경계에 놓인 모든 변은 테두리(0)여야 하고, 내부에서 맞닿는 변은 테두리가 아니어야 한다.

조각은 네 방향 중 어느 쪽으로든 회전할 수 있지만, 뒤집을 수는 없다. 네 변이 시계 방향으로 나열되므로, 조각을 회전하는 것은 이 목록을 순환 이동시키는 것과 같다.

아래 그림은 여섯 조각을 맞춘 한 가지 예이다. 맞닿은 변끼리는 같은 글자를 공유하고, 직사각형의 바깥쪽은 모두 테두리이다.

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

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

$R$과 $C$가 큰 퍼즐일수록 변에 쓰이는 글자가 더 다양해서 맞추기가 쉬운 편이다. 유효한 조립 방법은 항상 존재한다.

• 첫째 줄에 두 정수 $R$과 $C$가 주어진다.
• 다음 $R \times C$개의 줄에는 각각 한 조각의 정보가 주어진다: 정수 일련번호와 그 뒤에 시계 방향으로 나열된 네 변의 식별자.

조립된 퍼즐을 $R \times C$개의 줄로 출력한다. $C \cdot (i-1) + j$번째 줄에는 $i$행 $j$열(행과 열은 1부터 시작하며, 위에서 아래로 행 순서대로)에 놓인 조각의 정보를 출력한다: 일련번호 다음에 네 변을 위, 오른쪽, 아래, 왼쪽 순서로 출력한다.

규칙을 만족하는 조립 방법이 여러 가지일 수 있다. 그중 사전순으로 가장 작은 것을 출력하며, 그 기준은 다음과 같다. 각 조립을 위 순서에 따른 줄들의 나열로 보고, 한 줄을 튜플

$(\text{일련번호}, \text{위}, \text{오른쪽}, \text{아래}, \text{왼쪽})$

로 나타낸다. 두 조립을 이 튜플의 나열로서 앞에서부터 원소별로 비교한다. 일련번호는 정수로, 변의 글자는 문자값으로 비교한다. 이 순서에서 가장 작은 단 하나의 조립을 출력한다.