스네이크 큐브

스네이크 큐브는 나무로 만든 단위 정육면체 27개를 고무줄 하나에 꿰어 만든 퍼즐이다. 고무줄은 각 정육면체의 중심을 지나며, 한 면의 중심으로 들어와 다른 면의 중심으로 나간다. 첫 번째 정육면체에서는 들어오는 고무줄 없이 중심에서 고무줄이 시작하고, 마지막 정육면체에서는 나가는 고무줄 없이 중심에서 끝난다. 이웃한 두 정육면체는 서로 맞닿은 면의 중심을 축으로 자유롭게 돌릴 수 있다. 정육면체들이 고무줄로만 연결되어 있으므로, 퍼즐을 푸는 도중에 길게 늘어뜨릴 수도 있어 실로 고정한 경우에는 만들 수 없는 모양도 만들 수 있다.

27개의 정육면체는 두 가지 색으로 번갈아 칠해져 있으며, 두 색을 각각 대문자와 소문자로 나타낸다. 고무줄을 따라가는 순서대로 첫 번째 정육면체는 A, 두 번째는 a, 세 번째는 B, 네 번째는 b, ... 와 같이 이름을 붙이며, 27번째(마지막) 정육면체는 N이다. 즉 순서는 A, a, B, b, C, c, ..., M, m, N이다.

평면에 펼쳐 놓은 스네이크 큐브가 주어질 때, 이를 3×3×3 정육면체 모양으로 접었을 때의 모습을 구하는 프로그램을 작성하시오.

첫 15개 줄에 각각 15개의 문자가 주어지며, 퍼즐을 평면에 펼쳐 놓은 모습을 나타낸다. 빈 칸은 .으로 표시한다. 대문자 A부터 N까지 14개와 소문자 a부터 m까지 13개가 격자 위에 놓여 있고, 고무줄은 이들을 A, a, B, b, ..., N 순서로 잇는다.

주어지는 배치는 항상 올바르며, 다음을 모두 만족한다.

• 27개의 문자가 각각 정확히 한 번씩 나타난다.
• 순서에서 이웃한 두 정육면체는 격자에서도 상하좌우로 맞닿아 있다.
• 이웃한 두 정육면체는 서로 맞닿은 면을 통해 고무줄로 연결된다.

주어지는 퍼즐은 항상 3×3×3으로 접을 수 있다.

세 줄을 출력한다. 각 줄은 3×3×3으로 접은 정육면체의 한 층(3×3 면)을 나타내며, 첫째 줄이 첫째 층, 둘째 줄이 둘째 층, 셋째 줄이 셋째 층이다. 한 줄은 공백 하나로 구분한 세 개의 그룹으로 이루어지고, 각 그룹은 그 층의 한 행(정육면체 3개)을 나타낸다. 따라서 각 줄은 알파벳 9글자와 공백 2개, 모두 11글자로 이루어진다.

스네이크 큐브는 회전과 대칭에 따라 여러 방향으로 접을 수 있다. 올바른 접기 중에서, 출력 문자열 전체를 사전순으로 비교했을 때 가장 작은(사전순으로 가장 앞서는) 것을 출력한다.

각 정육면체가 직진 조각(고무줄이 마주 보는 두 면을 지나감)인지 꺾임 조각(고무줄이 이웃한 두 면을 지나감)인지는 퍼즐의 고유한 성질이며, 평면에 펼친 모습에서 이웃한 세 정육면체가 일직선인지 꺾이는지를 보면 알 수 있다. 접은 뒤에도 이 직진/꺾임 구조는 그대로 유지된다.