회전 게임

회전 게임은 정사각형 블록 24개를 담을 수 있는 # 모양의 판 위에서 진행한다. 각 블록에는 기호 1, 2, 3 중 하나가 적혀 있으며, 각 기호는 정확히 8개씩 있다.

입력에 주어지는 순서(위에서 아래로, 각 줄에서는 왼쪽에서 오른쪽으로)대로 24개의 칸에 1부터 24까지 번호를 매기자.

           1   2
           3   4
   5   6   7   8   9  10  11
          12  13
  14  15  16  17  18  19  20
          21  22
          23  24

중앙 사각형은 두 개의 가운데 세로줄과 두 개의 가운데 가로줄이 겹치는 여덟 칸 7 8 9 12 13 16 17 18으로 이루어진다.

처음에 블록들은 임의로 놓여 있다. 목표는 중앙 사각형의 여덟 칸에 적힌 기호가 모두 같아지도록 블록을 옮기는 것이다.

허용되는 유일한 이동은 일곱 칸짜리 네 줄(가운데 세로줄 두 개와 가운데 가로줄 두 개) 중 하나를 회전시키는 것이다. 한 줄을 회전시키면 그 줄의 일곱 블록이 각각 줄의 머리(가장 먼저 나열된 칸) 쪽으로 한 칸씩 이동하고, 머리에 있던 블록은 줄의 꼬리로 돌아간다. 여덟 가지 이동에는 A부터 H까지 이름이 붙어 있으며, 각 이동이 회전시키는 칸을 머리에서 꼬리 순서로 나열하면 다음과 같다.

A: 1 3 7 12 16 21 23      B: 2 4 9 13 18 22 24
C: 11 10 9 8 7 6 5        D: 20 19 18 17 16 15 14
E: 24 22 18 13 9 4 2      F: 23 21 16 12 7 3 1
G: 14 15 16 17 18 19 20   H: 5 6 7 8 9 10 11

즉 A/F는 왼쪽 세로줄을 위/아래로, B/E는 오른쪽 세로줄을 위/아래로, C/H는 위쪽 가로줄을 오른쪽/왼쪽으로, D/G는 아래쪽 가로줄을 오른쪽/왼쪽으로 회전시킨다. 각 이동은 해당 문자가 있는 방향으로 줄을 끌어당긴다.

입력은 최대 30개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 24개의 정수가 적힌 한 줄로, 초기 배치에서 블록들의 기호를 칸 번호 1–24 순서(위에서 아래로, 각 줄에서는 왼쪽에서 오른쪽으로)로 나열한 것이다. 정수는 하나의 공백으로 구분된다. 마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 와서 입력의 끝을 나타내며, 이 줄은 테스트 케이스가 아니다. 테스트 케이스 사이에 빈 줄은 없다.

각 테스트 케이스마다 두 줄을 출력한다.

첫 번째 줄에는 중앙 사각형을 모두 같은 기호로 만드는 이동 순서를 문자 A–H로, 사이에 공백 없이 출력한다. 이미 중앙 사각형이 모두 같은 기호여서 이동이 필요 없으면 대신 No moves needed를 출력한다.

두 번째 줄에는 이동을 마친 뒤 중앙 사각형을 채우는 기호(1, 2, 3 중 하나)를 출력한다.

이동 횟수가 가장 적은 해를 출력한다. 이동 횟수가 가장 적은 해가 여러 개이면 이동 순서가 사전순으로 가장 앞서는 것을 출력한다. 이 두 규칙에 의해 답은 유일하게 정해진다. 테스트 케이스 사이에 빈 줄을 출력하지 않는다.