틱택토

두 곰이 우편으로 틱택토를 하고 있다. 평범한 틱택토 게임은 그들에게 지루하기 때문에, 이 게임을 변형한 버전을 하고 있다. 규칙은 다음과 같다.

게임은 다음 필드에서 진행된다.

플레이어들은 번갈아 수를 둔다. 첫 수에는 플레이어가 어느 작은 필드의 어느 칸에든 자신의 말을 놓을 수 있다. 이후의 수에는 몇 가지 제한이 있다. 직전 수에서 상대 플레이어가 어떤 작은 필드의 좌표 (xl, yl)인 칸에 자신의 말을 놓았다면, 다음 수는 좌표가 (xl, yl)인 작은 필드의 칸 중 하나에 두어야 한다. 예를 들어 첫 수에서 플레이어가 중앙 필드의 왼쪽 아래 칸에 자신의 말을 놓았다면, 두 번째 플레이어는 다음 수에 왼쪽 아래 필드의 어떤 칸에 자신의 말을 놓아야 한다(첫 번째 테스트 케이스에 유의하라). 지정된 필드에 빈칸이 없다면, 플레이어는 어느 필드의 어느 빈칸에든 자신의 말을 놓을 수 있다.

게임의 현재 상태와 직전 수가 놓인 칸의 좌표가 주어진다. 현재 플레이어가 자신의 말을 놓을 수 있는 모든 칸을 찾아야 한다.

토끼 한 마리가 숲에서 우편배달부로 일하며, 곰들을 골탕 먹이는 것을 좋아한다. 토끼는 때때로 게임 필드를 조금 바꾸므로 게임의 현재 상태에 도달하는 것이 불가능할 수도 있다. 하지만 토끼가 바꾼 뒤에도 직전 수가 놓인 칸은 비어 있지 않다. 상태에 도달할 수 있는지 알아낼 필요는 없으며, 규칙에 따른 가능한 다음 수만 출력하면 된다.

처음 11개 줄에는 공백과 빈 줄로 구분된 9개의 작은 필드로 나뉘는 9행 9열 표에 대한 설명이 주어진다. 각 작은 필드는 공백과 빈 줄 없이 9개의 문자로 설명된다. 문자 "x"는 (ASCII- 코드 120) 첫 번째 플레이어의 말이 칸을 차지하고 있음을 의미하고, 문자 "o"는 (ASCII- 코드 111) 두 번째 플레이어의 말이 칸을 차지하고 있음을 나타내며, 문자 "."는 (ASCII- 코드 46) 빈칸을 나타낸다.

표 다음 줄에는 두 정수 x와 y가 (1 ≤ x, y ≤ 9) 주어진다. 이들은 표에서 직전 수가 놓인 칸의 좌표를 나타낸다. 표의 행은 위에서 아래로 번호가 매겨지고, 열은 왼쪽에서 오른쪽으로 번호가 매겨진다.

직전 수가 놓인 칸이 "x" 또는 "o"로 채워져 있음이 보장된다. 또한 빈칸이 적어도 하나 있음이 보장된다. 게임의 현재 상태에 도달할 수 있음은 보장되지 않는다.

현재 플레이어가 자신의 말을 놓을 수 있는 위치에 문자 "!"를 (ASCII- 코드 33) 표시하여 입력과 같은 형식으로 필드를 출력한다. 다른 모든 칸은 변경하지 않아야 한다.

첫 번째 테스트 케이스에서 첫 번째 플레이어는 중앙 필드의 왼쪽 아래 칸에 수를 두었으므로, 두 번째 플레이어는 왼쪽 아래 필드의 칸에만 말을 놓을 수 있다.

두 번째 테스트 케이스에서 직전 수는 아래쪽 중앙 필드의 왼쪽 위 칸에 놓였지만, 왼쪽 위 필드의 모든 칸이 차 있으므로 두 번째 플레이어는 어느 빈칸에든 자신의 말을 놓을 수 있다.

세 번째 테스트 케이스에서 직전 수는 중앙 필드의 중앙 칸에 놓였으므로 현재 플레이어는 중앙 필드의 어느 칸에든 자신의 말을 놓을 수 있지만, 그 필드는 이미 모두 차 있으므로 어디에든 수를 둘 수 있다. 이 게임 상태에는 도달할 수 없다는 점에 유의하라.