You are entering your robot into a simple game of strategy. The game is played on a grid and the robots take it in turns to move one space at a time (including diagonally) around the grid. When a robot moves into a square, that square is taken and nobody else can move into it for the duration of the game. When a robot is boxed in and cannot move on its turn, it is out. The winner is the Last Robot Standing.
Here's an example of the game in action on a small grid with robots. The positions of the robots are marked and and the shaded squares are taken and cannot be used again by either robot.
In this example, Robot is the Last Robot Standing. Note that Robot was boxed in on Move
H, but was not removed from the game at that point. Any robot that is able to move on its turn is safe for that turn. It is only on its next move (Move
J) that it is removed from the game. Note that if Robot had started out just one square to the left and used the same set of moves, it would have won.
The robots in the above game are choosing their moves from a hardwired "strategy" that tells them the order of moves to try. There are possible moves, numbered clockwise from to as shown at right. A robot's strategy can be represented as a list of numbers. Robot 's strategy is
2481377746543, and Robot 's strategy is
On Robot 's first turn (
A), it uses move , which is up and right. Then on its next turn (
C) it uses move (down and right). Then on its next turn (
E) it tries move (up and left) but is blocked, so it uses the next move in its strategy, which is (up). If a Robot ever runs out of moves in its hardwired strategy, it simply starts again from the beginning. Note that this can only work if each of the moves appears in each strategy at least once.
Using your evil hacking skills, you have found out the strategies of the other robots. Since you get to pick your starting position and you're moving last, you can figure out a winning start position.
The input will contain cases. Each case starts with a line of integers and . and are the number of rows and columns on the playing surface and is the number of robots in the competition . Your robot is the one. Following this are lines containing the integer starting position for each of the other robots (row then column, numbered from upwards), then lines containing the strategy for each robot (including your own). During the game, the robots take turns in the order they appear in the file, with your robot moving last.
Your job is to output a list of starting positions that will lead to a guaranteed win for your robot. If there is no such starting position, you should simply output the word
LOSE. Your output must be formatted exactly as shown below with no extra spaces or punctuation, but the order you output the starting positions for each case can be different from that shown.
Note that the sample input below only contains cases, but the data files will contain cases each.
5 5 2 3 2 2481377746543 62437428513 3 3 3 1 1 2 2 45362718 45362718 87654321 5 5 3 1 1 3 3 81726354 45362718 12345678 10 10 8 1 3 1 8 3 1 8 1 3 10 8 10 10 3 12345678 87654321 18273645 54637281 21436587 78563412 16372485 73265841
(1,2) (1,3) (2,3) (2,4) (3,1) (4,5) (5,2) (5,5) (3,3) (3,2) (4,2) (1,9) (4,9) (4,10) (5,7) (7,1) (7,2) (7,6) (7,7) (9,4)
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org