퍼즐 조각으로 정사각형 만들기

퍼즐 조각이 1개에서 5개까지 주어진다. 이 조각들을 배치하여, 가능하다면 4×4 정사각형을 만드는 프로그램을 작성하라.

조각은 회전하거나 뒤집을 수 없으며, 각 조각은 주어진 방향 그대로 사용해야 한다. 모든 조각을 빠짐없이 사용해야 하고, 조각들은 4×4 정사각형을 빈칸이나 겹침 없이 정확히 덮어야 한다. 어떤 조각 집합은 만들 수 있는 배치가 여러 개일 수도, 하나뿐일 수도, 전혀 없을 수도 있다.

입력에는 여러 개의 퍼즐(퍼즐 조각의 집합)이 들어 있다.

각 퍼즐의 첫 줄에는 그 퍼즐에 들어 있는 조각의 개수가 주어진다. 이어서 각 조각은, 조각의 행 수와 열 수를 나타내는 두 정수가 적힌 한 줄과, 그 행 수만큼의 모양 설명 줄로 주어진다. 모양 줄은 0과 1 문자로 이루어지며, 1은 조각이 실제로 채워진 칸을, 0은 빈 자리 표시일 뿐이다. 예를 들어 다음과 같은 조각은

2 3
111
101

2행 3열 크기이며, 그 모양대로 칸이 채워져 있다.

조각은 나타나는 순서대로 번호가 매겨진다. 즉 퍼즐의 첫 번째 조각이 1번, 그다음이 2번이다. 모든 조각은 유효하며 크기는 최대 4행 4열을 넘지 않는다.

한 퍼즐의 마지막 조각 다음 줄에는 그다음 퍼즐의 조각 개수가 주어지고, 이런 식으로 계속된다. 조각 개수 자리에 0이 나오면 입력이 끝난다.

각 퍼즐마다 4행 4열의 정사각형을 만든다. 1번 조각이 차지한 칸은 문자 1로, 2번 조각의 칸은 2로, 이런 식으로 바꾸어 네 줄을 출력한다.

만들 수 있는 정사각형이 여러 개라면 사전순으로 가장 작은 것을 출력한다. 네 줄을 위에서 아래로, 각 줄을 왼쪽에서 오른쪽으로 이어 붙인 16자 문자열로 보고, 그 문자열이 가장 작은 배치를 고른다.

정사각형을 만들 수 없으면 대신 No solution possible을 출력한다. 서로 다른 퍼즐의 출력은 빈 줄 하나로 구분한다.