Fire Lane
The ambulances
of Lilliput City Fire Department often have trouble to get across a
particularly busy crossroads in the down town. Frequently, ambulance drivers
have to shout orders asking drivers to remove cars from a certain lane in the
street, a special lane reserved
for emergency vehicles, the "Fire Lane".
To model the
situation, we consider an imaginary grid representing the street. Vehicles
occupy one or more cells in this grid. The vehicles always move forward (no
turns), towards the exterior of the grid, and towards a definite direction
(N,S,W,E). Unfortunately, there might be other vehicles blocking their way.
Your objective is to compute the necessary orders to clear the Fire Lane of
those blocking vehicles so that the ambulance can pass through.
The Fire Lane
consists of two distinguished consecutive columns in the grid. Consider, for
instance, the following grid:
. 0 0 0 0 . . .
. 4 1 1 1 . . .
. 4 . . . . . .
. . . 3 3 3 . .
. . 2 . . . . .
. . 2 . . . . .
. . 2 . . . . .
. . . . . . . .
In this picture,
the symbols '.' denote free cells, the numbers mark the vehicles, and the gray
shadow identify columns 3 and 4 as being the Fire Lane. Suppose that vehicles 0 and 3 are moving
East (right), vehicle 1 is moving West (left), vehicle 2 is moving South (down),
and vehicle 4 is moving North (up). Your program must compute which vehicles must
be moved away, and list them. In this example, the vehicles to be moved are
just 0, 3, 4 and 1, in this order.
Input
The first line
of the input contains two integers indicating the size of the grid (width and
height up to 100). Positions in the grid are represented by integer coordinates
x and y, starting
from 0, where x denotes the column and y the row, with origin the upper left corner. The second line of the
input contains an integer N that indicates the
number of vehicles to be listed. The third line contains an integer that
indicates the x coordinate of the left column of
the Fire Lane (which always has 2 columns). The next N lines give information for each of the N vehicles in the grid. For each line, describing a vehicle, there
are two integers x, y indicating its coordinates in the grid, an integer for the length
of the vehicle (the vehicles are 1 cell wide), and a character for the
direction (N, S, W or E) towards which the vehicle extends and may move, starting from its
position x, y.
The numeric code of a vehicle is given by its position in the input sequence,
starting with 0.
Output
The output of
your program is a list of vehicle numbers, each number in a separate line, to
present a solution, or the word "Jammed" if there are no solutions to the given
problem. In case there is a solution, it should refer just to vehicles that
need indeed to be removed. To list all the vehicles to be removed, you should
at each step select among the vehicles that may be moved away (i.e., that are
not blocked) the one with the least code number.
Sample Input
8 8
5
3
1 0 4 E
4 1 3 W
2 4 3 S
3 3 3 E
1 2 2 N
Sample Output
0
3
4
1