Domineering

Problem

Two players play the game of Domineering on an $8 \times 8$ board.

1. Board and Components

The board consists of $64$ cells arranged from row $1$, column $1$ to row $8$, column $8$. A cell at the $x$-th row and $y$-th column is denoted as $(x, y)$. Initially, all cells on the board are empty, and each cell $(x, y)$ contains a single integer $A_{x, y}$ uniformly distributed between $0$ and $3$, inclusive.

Below is an example of the initial board.

Initially, the first player starts the game with $0$ points, and the second player starts with $2.5$ points.

2. Gameplay

The game begins with the first player, and the two players take turns alternately.

During their turn, the first player can place a $1 \times 2$ domino covering two horizontally adjacent empty cells, or select PASS. When placing a domino, the player must simultaneously cover the empty cells $(x, y)$ and $(x, y + 1)$ on the board, and earns points equal to the sum of the integers written on the two cells.

Below is an example of the first player placing a domino covering $(4, 5)$ and $(4, 6)$.

During their turn, the second player can place a $2 \times 1$ domino covering two vertically adjacent empty cells, or select PASS. When placing a domino, the player must simultaneously cover the empty cells $(x, y)$ and $(x + 1, y)$ on the board, and earns points equal to the sum of the integers written on the two cells.

Below is an example of the second player placing a domino covering $(5, 4)$ and $(6, 4)$.

3. Game End

The game ends when both players select PASS consecutively, or when there are no valid positions left for either player to place a domino.

At the end of the game, the player with the higher score wins.

Please design an AI to become the ultimate winner of the board!

Input

Before the judge program and the agent begin communicating, the following input is provided over $8$ lines.

• On the $i$-th line $(1 \le i \le 8)$, the integers $A_{i, 1}, A_{i, 2}, \cdots, A_{i, 8}$ representing the numbers written on each cell of the board are given, separated by spaces. $(0 \le A_{i, j} \le 3)$

Afterward, the judge program communicates with the agent using single-line text commands as follows:

• In the MOVE and OPP commands, x and y are integers. If x and y are not both -1, $(x, y)$ represents the coordinates of the cell with the smaller row and column numbers among the two cells covered by the placed domino.
• my_time, opp_time, and time are integers representing time in milliseconds.
• After every output, you must print a newline character and flush the buffer.
• Failure to output within the time limit results in a Time Limit Exceeded (TLE) verdict.
• Outputting an invalid format or an illegal move during a TURN command results in a Runtime Error (RE) verdict.

Example