Light-Cycle Race

Light-cycle racing involves two motorcycles that drive along the edges of a two-dimensional square grid. As each light cycle traverses its path, it leaves behind a wall along the path it travels. Two players compete by driving simultaneously from two different starting points. A player may die in three ways: (1) driving outside the grid, (2) hitting a wall (either his own or his opponent's), or (3) colliding with the other light cycle.

A player's path is described as follows. First, the (x, y) coordinates of the player are given. Initially, the player faces east, the same direction as the positive x-axis. The path is a number of segments, where each segment has the form (T, k). T is the direction turned, either S, L, or R, meaning Straight, Left, or Right. The integer k is the distance to travel after turning. So "R 6" means turn right, relative to the current direction, and travel 6 units.

For example, take a grid of width 10 and height 8, and a player that starts at (2, 3) and executes the segments "L 4", "R 6", and "R 2". The result is shown in Figure 1(a). The cycle moves one grid square per second, and the labels on the points give the time the cycle arrives at each point.

Figure 1: Example of a light cycle path.

The program reads the dimensions of the driving area and the motion descriptions of the two players. Each description contains the player's initial (x, y) coordinates, the number of motion segments, and the list of segments. The program simulates the game starting at time 0 and stops at whichever comes first: the first time either player dies (both may die at the same time), or the point where neither has died and one player completes its motion. When the game stops, the program outputs the finish time, the player positions, and whether each player is alive or dead. Figure 1(b) shows an example. There are two players, 0 and 1. The game ends at time 4 when player 1 hits the wall of player 0. Any motion segments given after the end of the game are ignored.