Renju

Problem

Two players play a game of Omok on a $15 \times 15$ board.

The board consists of $225$ cells, ranging from row $1$ and column $1$ to row $15$ and column $15$. A cell at the $x$-th row and $y$-th column is denoted as $(x, y)$.

Each cell can be in one of three states: an empty cell ., the first player's stone B, or the second player's stone W. Initially, the stones are arranged as follows:

---

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

• During their turn, a player can select an empty cell $(x, y)$ to place their stone, or select PASS.
• On the first turn, the first player cannot select PASS and must place a stone at $(8, 8)$.
• On the second turn, the second player cannot select PASS and must place a stone at $(x, y)$ where $7 \le x, y \le 9$.
• On the third turn, the first player cannot select PASS and must place a stone at $(x, y)$ where $6 \le x, y \le 10$.

The figure above is an example of the first player placing a stone at $(10, 8)$.

1. TERMS AND DEFINITIONS

The key terms that make up the Renju rules are defined as follows:

1. ROW: A combination of empty cells and stones placed consecutively in a diagonal, vertical, or horizontal line. A ROW must contain at least one stone, and all stones within the ROW must be either all B or all W. Both ends of the ROW must be blocked by the edge of the board, a stone of a different color, or an empty cell.

• A and B are ROWs.
• C is not a ROW because one of its ends is a stone of the same color.

2. UNBROKEN ROW: A ROW with no empty cells inside.

• B is not an UNBROKEN ROW because there is an empty cell inside.
• D is an UNBROKEN ROW.

3. FIVE IN A ROW: An UNBROKEN ROW consisting of $5$ stones.

• E is a FIVE IN A ROW.

4. OVERLINE: An UNBROKEN ROW consisting of $6$ or more stones.

• F is an OVERLINE consisting of $6$ stones.

5. FOUR: A ROW consisting of $4$ stones to which one more stone can be added to create a FIVE IN A ROW.

• G and H are FOURs because one more stone can be added to create a FIVE IN A ROW.

6. STRAIGHT FOUR: An UNBROKEN ROW consisting of $4$ stones where there are $2$ ways to add one more stone to create a FIVE IN A ROW.

• H is a STRAIGHT FOUR because there are $2$ ways to add one more stone to create a FIVE IN A ROW.
• G is not a STRAIGHT FOUR because there is only $1$ way to add one more stone to create a FIVE IN A ROW.

7. THREE: A ROW consisting of $3$ stones where adding one more stone does not create a FIVE IN A ROW but can create a STRAIGHT FOUR.

• I and J are THREEs because adding one more stone does not create a FIVE IN A ROW while it can create a STRAIGHT FOUR.
• K, L, and M are not THREEs because adding one more stone cannot create a STRAIGHT FOUR.
• N is not a THREE because adding one more stone can create a STRAIGHT FOUR, but it simultaneously creates a FIVE IN A ROW.

8. DOUBLE FOUR: Placing a stone in an empty cell such that $2$ or more different FOURs containing that cell are created.

• O is a DOUBLE FOUR because $2$ or more different FOURs are created.

9. DOUBLE THREE: Placing a stone in an empty cell such that $2$ or more different THREEs containing that cell are created.

• P is not a DOUBLE THREE because only one THREE is created.
• Q is a DOUBLE THREE because $2$ or more different THREEs are created.

2. FORBIDDEN MOVES

To reduce the advantage of the first player over the second player, the Renju rules apply the following additional rules to the first player.

1. The first player cannot create an OVERLINE, DOUBLE FOUR, or DOUBLE THREE unless it simultaneously creates a FIVE IN A ROW.

• The first player cannot play at A because it is a DOUBLE FOUR.
• The first player cannot play at B because it is an OVERLINE.
• The first player can play at C because although it is a DOUBLE FOUR, it simultaneously creates a FIVE IN A ROW.
• The first player cannot play at D and E because they are DOUBLE THREEs.
• The first player cannot play at F, H, and I because they are DOUBLE THREEs.
• The first player cannot play at G because it is a DOUBLE FOUR.

2. However, Black's DOUBLE THREE is allowed when, among the THREEs created according to Article 9.3 of the Renju rules, the cell where a stone must be added to make a STRAIGHT FOUR becomes an OVERLINE or DOUBLE FOUR, resulting in $1$ or fewer valid THREEs. It is also allowed if the cell where a stone must be added to make a STRAIGHT FOUR becomes another forbidden DOUBLE THREE, resulting in $1$ or fewer valid THREEs. To check whether another DOUBLE THREE is allowed, you must first evaluate it based on the preceding criteria, and then continue simulating the creation of STRAIGHT FOURs to determine any cascading DOUBLE THREEs in the same manner.

• The first player can play at J because the cell where a stone must be added to make the horizontally created THREE into a STRAIGHT FOUR becomes an OVERLINE, leaving only $1$ valid THREE.
• The first player can play at K because the cell where a stone must be added to make the diagonally (bottom-right) created THREE into a STRAIGHT FOUR becomes a DOUBLE FOUR, leaving only $1$ valid THREE.
• The first player can play at L because the cell where a stone must be added to make the horizontally created THREE into a STRAIGHT FOUR becomes an unallowed DOUBLE THREE, leaving only $1$ valid THREE.

3. WIN OF A GAME

The game ends when any of the following conditions are met:

• If the first player creates a FIVE IN A ROW, the first player wins.
• If the second player creates a FIVE IN A ROW or an OVERLINE, the second player wins.
• If both players consecutively select PASS, the game ends in a draw.

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

NOTE.

The Renju rules additionally apply the opening rules of Articles 12.1~12.9 to further reduce the advantage of the first player over the second player, but for the convenience of implementation in this problem, the opening rules have been intentionally omitted.

Input

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

• x, y are integers.
• 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