Reversi

Two players take turns placing stones on an $8 \times 8$ board and flipping the opponent's stones.

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

Each cell is in one of three states: empty ., black stone B, or white stone W. At the start of the game, white stones are placed on $(4,4)$ and $(5,5)$ and black stones on $(4,5)$ and $(5,4)$, and all other cells are empty.

The game starts with the first player, who plays black, and the two players take turns alternately. On your turn, you choose one empty cell $(r,c)$ and place a stone of your color there.

The cell where you place a stone must satisfy the following conditions.

• In at least one of the eight horizontal, vertical, and diagonal directions from that cell, there must be one or more consecutive opponent stones.
• The cell right after those consecutive opponent stones must hold one of your own stones. If an empty cell or one of your own stones comes in between, opponent stones beyond it are not included.

When a player places a stone, the following steps happen in order.

• The current player's stone is placed on the chosen empty cell.
• All eight directions from the newly placed stone are checked to find every opponent stone sandwiched in a direction that satisfies the conditions above.
• All of those stones are flipped to the current player's color. If the conditions hold in several directions, the stones in all of those directions are flipped.

Even if flipping causes opponent stones to become sandwiched in another direction, they are not flipped further. Only the directions extending directly from the newly placed stone are checked.

For example, if black places a stone on $(3,4)$ on the first turn, the white stone on $(4,4)$ is flipped to black. The cells black can choose at the start are $(3,4)$, $(4,3)$, $(5,6)$, and $(6,5)$.

If there is no cell where you can place a stone on your turn, you pass. If there is at least one cell where you can place a stone, you cannot pass. You cannot choose a cell that already has a stone or a cell where no opponent stone would be flipped.

If neither player can place a stone, the game ends even if empty cells remain on the board.

When the game ends, the player with more stones of their color wins. If both players have the same number of stones, the game is a draw.

Design an AI that flips the opponent's stones, holds more stones, and becomes the final winner!

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

• turn, r, and c are integers.
• turn is a turn number that counts the actions of both players, starting from $1$. It increases by $1$ even when a player passes.
• board is a string of length $64$. Starting from row $1$, column $1$, each row is listed from left to right, and the rows are joined from the top row to the bottom row.
• Each character of board is one of empty ., black stone B, or white stone W. The state of $(r,c)$ is the $8(r-1)+c$-th character from the start of the string.
• r and c are between $1$ and $8$ inclusive and denote the row counted from the top and the column counted from the left, respectively.
• On each of your turns, the judge sends the entire current board. The opponent's previous action is already reflected in this board, and no input is given during the opponent's turn.
• Each player has a total of $5{,}000\text{ms}$ for the entire game, from which the response times for READY and all of your TURN responses are deducted. Time spent waiting for the opponent's response is not deducted.
• Your remaining time is not given as a separate value in the input. A new time limit is not granted each turn.
• A separate $5{,}000\text{ms}$ limit also applies to the CPU time used by the whole program.
• After every output, print a newline and then flush the buffer. Respond to each request with exactly one line made of the specified tokens.
• If you fail to respond within your remaining total time or your program terminates abnormally, you lose immediately.
• If you print a string that does not match the output format or illegal coordinates, you lose immediately. You also lose immediately if you print PASS while there is a cell where you can place a stone.
• When the game ends, the judge terminates the player's program without sending any further commands.

The following is an example of communication between the two players and the judge, starting from the initial board.

When the first player places a stone on $(3,4)$, the white stone on $(4,4)$ is flipped to black. Next, when the second player places a stone on $(3,3)$, the black stone on $(4,4)$ is flipped to white. Then, when the first player places a stone on $(3,2)$, the white stone on $(3,3)$ is flipped to black.

If there is no cell where you can place a stone on your turn, print PASS instead of MOVE r c. Once the game ends, no more input is given.

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