Problem B. Gomoku ≡

Statement

This is an interactive problem.

Gomoku is a two-player game on a two-dimensional grid. Each cell of the grid can be either empty, contain the first player’s mark (black), or contain the second player’s mark (white), but not both. Initially the entire grid is empty. Two players make alternating moves, starting with the first player. At each move, a player can put her mark into exactly one empty cell. The first player to have her five adjacent marks in a single row wins. The winning row can be either vertical, horizontal or diagonal.

Position where the second player (white marks) had won.

The players use a 19 × 19 grid in this problem. If the entire grid gets filled with marks but no player has won, the game is declared a draw.

The first player uses the following strategy: as the first move, she puts her mark into the center cell of the grid. At every other move, she picks such a move that maximizes the score of the resulting position.

In order to find the score of a position, the first player considers all possible places where the winning combination might eventually form — in other words, all horizonal, vertical and diagonal rows of five consecutive cells on the board (of course, they may overlap each other). If such a row contains both the first player’s marks and the second player’s marks, it is disregarded. If such a row contains no marks, it is disregarded as well. For each row with exactly k (1 ≤ k ≤ 5) marks of the first player and no marks of the second player, add 50^2k − 1 to the score of the position. For each row with exactly k marks of the second player and no marks of the first player, subtract 50^2k from the score of the position. Finally, add a random integer number between 0 and 50² − 1 to the score. This random number is chosen uniformly.

In case when several moves of the first player have equal scores (such ties are quite rare because of the random addition mentioned above), the first player picks the one with the smallest x-coordinate, and in case of equal x-coordinates, the one with the smallest y-coordinate.

Your task is to write a program that plays the second player and beats this strategy.

Your program will play 100 games against the strategy described above, with different seeds of random generator. Your program must win all these games.

Interaction protocol

On each step, your program must:

1. Read numbers x and y from the input.
2. If both these numbers are equal to  − 1 then the game is over and your program must exit.
3. Otherwise these numbers are the coordinates of the first player’s move (1 ≤ x, y ≤ 19).
4. Print the coordinates of the move of the second player, followed by line end. Don’t forget to flush the output buffer.

Note

There are many variations of Gomoku rules in the world. Please only consider the rules described in this problem statement.

In the example below the first player does not use the strategy from the problem statement. The example is given only to illustrate the interaction format.

Final position from the example.

Sample tests

10 10
10 11
10 12
10 13
9 10
9 11
9 9
11 13
-1 -1

11 10
11 11
10 9
10 14
8 9
11 9
11 12
11 8