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: .0000... .4111... .4...... ...333.. ..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 input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. 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 For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.
2/2 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 88 5 3 104E 413W 243S 333E 122N Sample Output 0 3 4 1