Robots

Robots is a single-player game played on a $31 \times 31$ board. The board is divided into $1 \times 1$ cells arranged in $31$ rows and $31$ columns. Each cell is identified by $(r, c)$, where $r$ is the row and $c$ is the column, both numbered from $1$. A cell may be empty, occupied by you, occupied by a robot, or occupied by debris. Your goal is to move so that every robot is destroyed before the robots destroy you.

Initially you occupy cell $(15, 15)$, and there are $R$ robots $(1 \le R \le 50)$ placed in $R$ distinct cells other than $(15, 15)$. Every other cell is empty. You are also given a list of $T$ $(0 \le T \le 20)$ cells that are possible teleport destinations. You move first, and afterwards you and the robots move alternately.

On your turn you may do exactly one of the following.

• Walk to an adjacent cell in one of the eight compass directions, if that cell is empty.
• Walk to an adjacent cell that contains debris by pushing the debris one more cell along the same direction, provided the cell the debris is pushed into does not already contain debris. If that cell contains a robot, the robot is destroyed.
• Teleport to one of the listed destinations, which must be an empty cell.
• Remain stationary.

You may never make a move that would push you or any debris off the board.

When the robots move, each robot steps to the adjacent cell (in one of the eight compass directions, even if it is not empty) that is closest to your current cell, i.e. your cell after your latest move. The distance between $(r_1, c_1)$ and $(r_2, c_2)$ is $|r_1 - r_2| + |c_1 - c_2|$. All robots step at the same time. If two or more robots step onto the same cell, or a robot steps onto a cell that already contains debris, all of those robots are destroyed. A destroyed robot becomes debris.

You lose if any robot steps onto your current cell, even if several robots do so and destroy one another. You win if every robot has been destroyed and none stepped onto your current cell.

To survive as long as possible you consider only moves that do not lead to an immediate loss (a loss before your next turn). The strategy is: walk to a cell (or stay put) so that the number of robots remaining after your move and the robots' following move is as small as possible. Break ties by choosing the move that maximizes the minimum distance from your destination to the remaining robots just before your next turn. Break further ties by the smallest destination row, and finally by the smallest destination column.

If no walking or staying move avoids an immediate loss, you teleport to the first still-unused legal destination in the list that does not lead to an immediate loss, always scanning the list from the beginning. If no such destination exists, you remain stationary and lose.

Implement this strategy and report how the game turns out.

The input contains several test cases. Each test case begins with a line containing two integers $R$ and $T$ separated by a space. The next $R$ lines each contain two integers, the row and column of a robot's starting cell; the robots start on distinct cells, none of which is $(15, 15)$. The following $T$ lines each contain two integers, the row and column of a teleport destination, in the order they should be tried. The input ends with a test case in which $R = T = 0$; this case must not be processed.

For each test case print the case number on its own line in the format shown, starting from $1$: Case k:.

Every time you teleport, print a line of the form

Move m: teleport to (r,c)

where $m$ is the number of moves you have made so far, including this one, and $(r,c)$ is the teleport destination.

Then print the outcome. If you win, print

Won game after making m moves.
Final position: (r,c)
Number of cells with debris: d

where $m$ is the number of moves made when you won, $(r,c)$ is your final cell, and $d$ is the number of cells containing debris. Always use the word "moves", even when $m = 1$.

If you lose, print

Lost game after making m moves.
Final position: (r,c)
Number of cells with debris: d
Number of robots remaining: n

where $m$ is the number of moves made when you lost, $(r,c)$ is the cell where you were destroyed, $d$ is the number of cells containing debris, and $n$ is the number of robots still remaining. Always use the word "moves", even when $m = 1$.

Separate the output for consecutive test cases with a blank line.