직소 퍼즐 맞추기

직소(조각) 퍼즐을 맞추는 프로그램을 작성한다. 입력에는 퍼즐의 크기, 조각의 크기, 그리고 모든 조각이 주어진다. 각 조각은 ASCII 문자로 그려져 있다. 프로그램은 조각들을 올바른 위치에 배치한 완성된 퍼즐을 출력해야 한다.

첫째 줄에 세 정수 $N$, $H$, $W$가 주어진다. 각각 퍼즐의 한 변에 놓인 조각 수(퍼즐은 항상 $N \times N$ 조각으로 이루어진 정사각형이다), 조각의 높이, 조각의 너비이다. 모든 조각의 크기는 같다. 범위는 $2 \le N \le 10$, $1 \le H, W \le 25$이다. 예를 들어 2 2 3은 각 조각이 높이 $2$, 너비 $3$ 문자인 $2 \times 2$ 퍼즐을 뜻한다.

이어서 $N \times N$개의 조각이 임의의 순서로 주어진다. 각 조각은 그 이미지(정확히 $H$줄, 각 줄 $W$문자)와 그다음 줄에 놓인, $[-5, 5]$ 범위의 네 정수로 이루어진다. 이 네 값은 순서대로 위, 왼쪽, 아래, 오른쪽 변의 모양이다. 값 $0$은 곧은(바깥쪽) 변을 뜻한다. 두 변은 값의 부호가 반대이고 합이 $0$일 때 정확히 맞물린다(예: $+5$는 $-5$와, $+4$는 $-4$와 맞물린다). 조각은 회전할 수 없으며, 네 변의 값이 모두 같은 두 조각은 존재하지 않는다(모든 조각은 서로 다르다). 조각과 조각 사이는 빈 줄 하나로 구분된다.

공백 문자(ASCII 32)도 조각을 이루는 유효한 문자이며, 줄 끝이나 한 줄 전체를 포함해 어디에나 나타날 수 있고, 해당 위치에 그대로 입력에 포함된다. 모든 조각은 문자(ASCII 32~127)로 채워진 직사각형 블록이므로, 공백도 다른 문자와 똑같이 취급한다.

완성된 퍼즐을 출력한다. $N \times N$개의 조각을 배치하는 방법은 유일하다. 모든 바깥쪽 변(값 $0$)은 퍼즐의 테두리에 놓이고, 각 조각의 오른쪽 변과 그 오른쪽 이웃 조각의 왼쪽 변의 합이 $0$이며, 각 조각의 아래쪽 변과 그 아래 조각의 위쪽 변의 합이 $0$이 되도록 맞춘다. 이렇게 완성된 그림, 즉 $N \cdot H$줄, 각 줄 $N \cdot W$문자를 출력한다. 입력에는 항상 정확히 하나의 해가 존재한다.