Domineering

문제

$8 \times 8$ 크기의 보드 위에서 두 플레이어가 도미니어링 게임을 진행합니다.

1. 보드 및 구성 요소

보드는 $1$행 $1$열부터 $8$행 $8$열까지 $64$개의 칸으로 구성되며, $x$행 $y$열의 칸을 $(x, y)$로 표기합니다. 초기 보드의 모든 칸은 빈 칸으로 주어지며, 각 칸 $(x, y)$에는 $0$ 이상 $3$ 이하의 정수 $A\_{x, y}$가 하나씩 적혀있습니다.

다음은 초기 보드의 예시입니다.

초기에 선공 플레이어는 $0$점으로, 후공 플레이어는 $2.5$점으로 게임을 시작합니다.

2. 게임 진행

게임은 선공 플레이어부터 시작해 두 플레이어가 번갈아 턴을 진행합니다.

선공 플레이어는 자신의 턴에 가로로 인접한 두 빈 칸을 덮는 $1 \times 2$ 크기의 도미노를 놓거나, PASS를 선택할 수 있습니다. 도미노를 놓는 경우, 플레이어는 보드 위의 빈 칸 $(x, y)$와 $(x, y + 1)$을 동시에 덮어야 하며, 두 칸에 적혀있던 정수의 합만큼 점수를 획득합니다.

다음은 선공 플레이어가 $(4, 5)$와 $(4, 6)$을 덮는 도미노를 놓는 예시입니다.

후공 플레이어는 자신의 턴에 세로로 인접한 두 빈 칸을 덮는 $2 \times 1$ 크기의 도미노를 놓거나, PASS를 선택할 수 있습니다. 도미노를 놓는 경우, 플레이어는 보드 위의 빈 칸 $(x, y)$와 $(x + 1, y)$을 동시에 덮어야 하며, 두 칸에 적혀있던 정수의 합만큼 점수를 획득합니다.

다음은 후공 플레이어가 $(5, 4)$와 $(6, 4)$를 덮는 도미노를 놓는 예시입니다.

3. 게임 종료

게임은 두 플레이어가 연속해서 PASS를 선택하거나, 두 플레이어 모두 도미노를 놓을 수 있는 위치가 없는 경우 종료됩니다.

게임이 종료된 시점에 점수가 더 큰 플레이어가 승리합니다.

보드의 최종 승자가 되기 위한 AI를 설계해주세요!

입력

채점기와 플레이어가 통신을 시작하기 전 $8$개 줄에 걸쳐 다음의 입력이 주어집니다.

• $i(1 \le i \le 8)$번째 줄에 보드의 각 칸에 적힌 정수를 의미하는 $A\_{i, 1}, A\_{i, 2}, \cdots, A\_{i, 8}$이 공백으로 구분되어 주어집니다. $(0 \le A\_{i, j} \le 3)$

이후 채점기는 다음의 한 줄 단위로 플레이어와 통신합니다.

• move와 opp 명령어에서 x, y는 정수이며, x, y가 모두 -1이 아닌 경우는 플레이어가 놓은 도미노가 덮는 두 칸 중 행 번호, 열 번호가 작은 칸의 좌표가 $(x, y)$임을 의미합니다.
• my_time, opp_time, time은 정수이며, 시간은 밀리초(millisecond) 단위로 주어집니다.
• 모든 출력 후에는 개행문자를 출력한 뒤 버퍼를 flush해야 합니다.
• 시간 제한이 있는 명령에서 출력을 제한 내에 수행하지 않으면 시간 초과(TLE) 판정을 받습니다.
• 출력 형식에 맞지 않는 문자열을 출력하거나, TURN 명령어가 주어질 때 합법적이지 않은 수를 출력하면 런타임 에러(RE) 판정을 받습니다.

예시