프리무브 체크메이트

주의: 이 문제의 프리무브 설명은 널리 쓰이는 체스 사이트의 프리무브와 다릅니다.

인터넷에서 체스를 두고 있다. 킹과 퀸 한 개씩을 가지고 있고, 상대는 킹 한 개만 남아 있다. 남은 시간이 없어서 한 수도 둘 수 없다.

다행히 프리무브 기능이 있다. 동작 방식은 다음과 같다. 보드에서 수를 여러 개 입력한다. 각 수는 시작 칸과 도착 칸만으로 표시되며, 기물이 시작 칸에 그대로 있을 필요는 없다. 입력한 수는 큐에 저장된다. 큐에 수를 추가할 수 있는 때는 상대가 수를 둔 뒤뿐이다.

상대가 수를 두면 프리무브 큐가 비어 있지 않은 경우 큐에서 수를 하나씩 꺼낸다. 꺼낸 수가 유효하지 않으면 건너뛴다. 유효한 수는 곧바로 보드에 적용되며, 시계 시간은 줄지 않는다.

현재 위치에서 킹은 c3, 퀸은 d4에 있다. 상대 킹은 오른쪽 위 사분면의 칸 중 하나에 있다. 가능한 칸은 e5, e6, e7, e8, f5, f6, f7, f8, g5, g6, g7, g8, h5, h6, h7, h8이다. 정확히 어느 칸인지는 기억나지 않는다.

지금은 상대의 차례다. 시계 시간이 없으므로 곧바로 체크메이트로 이어지는 프리무브 큐를 입력해야 한다. 체크메이트는 50수 안에 해야 하며, 이 횟수에는 여러분의 수만 포함된다. 큐에는 최대 500개의 수를 넣을 수 있다. 그중 유효하지 않아 건너뛰는 수가 있을 수 있으며, 건너뛴 수는 횟수에 포함되지 않는다.

테스트는 하나뿐이다. 입력에는 c3 d4라는 줄이 들어 있다. 이 줄은 읽을 필요가 없다.

수의 순서를 출력한다. 각 수는 4글자 문자열이다. 앞의 2글자는 시작 칸, 뒤의 2글자는 도착 칸을 나타낸다. 수의 예는 a1b1, c6f3이다.

샘플 테스트는 킹이 f6, 퀸이 e5에 있고, 상대 킹이 f8, g8, h8, h7, h6 중 한 칸에 있는 위치를 나타낸다. 테스트 시스템에는 이런 테스트가 없다.

샘플 테스트에서 흑이 수를 둔 뒤에도 흑 킹은 f8, g8, h8, h7, h6 중 한 칸에만 있을 수 있다. 가능한 마무리는 다음과 같다.

• 흑 킹이 f8에 있는 경우: 1. Kf6-g6 Kf8-g8 2. Qe5-g7
• 흑 킹이 g8에 있는 경우: 1. Kf6-g6 Kg8-f8 2. Qe5-g7 Kf8-e8 3. Qg7-c7 Ke8-f8 4. Qc7-f7
• 흑 킹이 h8에 있는 경우: 1. Kf6-f7 Kh8-h7 2. Qe5-g7
• 흑 킹이 h7에 있는 경우: 1. Kf6-f7 Kh7-h6 2. Qe5-g7 Kh6-h5 3. Qg7-g3 Kh5-h6 4. Qg3-h4
• 흑 킹이 h6에 있는 경우: 1. Kf6-f7 Kh6-h7 2. Qe5-g7

앞의 두 경우에는 큐의 처음 네 수가 유효하지 않아 건너뛴다는 점에 유의한다.