Icebreaking

Two players play an ice-breaking game on a $9 \times 9$ ice board.

The ice board consists of $1 \times 1$ cells arranged in $9$ rows and $9$ columns. Rows are numbered from $0$ to $8$ from top to bottom, and columns are numbered from $0$ to $8$ from left to right. The cell in row $r$ and column $c$ is denoted $(r,c)$.

Each cell is in one of the following states: empty ice, a hole #, a cell taken by the first player a, or a cell taken by the second player b. Only empty ice can be selected. Holes and cells already taken by a player cannot be selected again.

The board has exactly $9$ holes. Their positions are determined by the seed given for each match, and each hole is on a different cell. Both players receive the same board as input before the game starts.

Each of the $72$ empty ice cells other than the holes has a score of $-2$, $-1$, $0$, $1$, or $2$ written on it. The ice scores are also determined by the seed. Taking ice with a negative score can lower your total score.

The game starts with the first player A, and A and B take turns alternately. On your turn, you select one currently empty ice cell $(r,c)$.

When a player selects an empty ice cell, the following steps happen in order.

• The current player takes the selected cell and gains the score written on it.
• Consider the region of empty ice, connected up, down, left, and right, that the cell belonged to just before it was selected.
• If the region splits into two or more parts once the selected cell is gone, compare the sizes of the connected components.
• The largest connected components remain as they are, and all smaller connected components become the current player's cells. This is called a chain capture.
• The scores written on all chain-captured cells are added to the current player's total score.

Connectivity of empty ice is determined using only the four directions up, down, left, and right. Cells that touch only diagonally are not connected. Holes and taken cells are not part of any connected region of empty ice.

If several connected components share the largest size, all of them remain. If all the split components have the same size, no cells are chain-captured.

For example, if one region of empty ice splits into three regions of sizes $12$, $5$, and $5$, both regions of size $5$ are chain-captured. If it splits into three regions of sizes $7$, $7$, and $3$, only the region of size $3$ is chain-captured.

The following actions are invalid.

• Producing output that does not match the output format
• Outputting coordinates outside the board
• Selecting a hole or a cell that is already taken

A player who makes an invalid action loses immediately.

The game ends when any of the following conditions is met.

• No selectable empty ice remains

• A player makes an invalid action

• A player exceeds the time limit or has a runtime error

Design an AI that becomes the final winner by considering both the board's connectivity and the score of each cell!

Before the game starts, the judge gives both players the same initial board as the following $9$ lines.

cell_0,0 cell_0,1 ... cell_0,8
...
cell_8,0 cell_8,1 ... cell_8,8

Each line contains the $9$ cells of that row, separated by spaces.

• If $(r,c)$ is an ice cell, cell_r,c is the score of that cell, one of -2, -1, 0, 1, 2.
• If $(r,c)$ is a hole, cell_r,c is #.
• Of the $81$ tokens in total, exactly $9$ are #, and the remaining $72$ tokens are ice scores.
• Hole positions and ice scores are determined by the match seed. Both players always receive the same initial board.

Once the initial state has been sent, the command exchange begins.

The judge communicates with the players one line at a time as follows.

• r, c, my_time, opp_time, and time are integers.
• r and c are between $0$ and $8$ inclusive and denote the row and column, respectively.
• my_time, opp_time, and time are given in milliseconds.
• Each player has their own independent total of $5{,}000\text{ms}$. Time used by one player does not reduce the opponent's remaining time.
• Response time for READY and all of your TURN responses is cumulatively deducted from your total time. There is no separate fixed time limit per turn.
• Cumulative CPU time over the program's entire lifetime is also limited to $5{,}000\text{ms}$ per player. Startup processing, background computation during the opponent's turn, and computation in child processes all count toward this CPU total.
• You must apply your own MOVE and the opponent's OPP under the same game rules to update the board and scores inside your program.
• The r and c given by OPP are always the legal coordinates the opponent just selected.
• After every output, print a newline and then flush the buffer.
• Print debug messages only to standard error. Do not print anything other than protocol responses to standard output.
• If you fail to respond within your remaining total time or use up the cumulative CPU total, you receive a time limit exceeded (TLE) verdict.
• Printing a string that does not match the output format, or printing illegal coordinates in response to a TURN command, counts as an invalid action, and you lose immediately. After an invalid action, the opponent receives neither OPP nor the next TURN.

After receiving the $9$ lines of the initial board, communication can proceed as follows. The table below omits the initial $9$ lines.

• CPP20 : main.cpp
• PYTHON3, PYPY3 : main.py