An important soccer match is about to begin between long time rival teams A and B. Team B won the toss for the ball, so a player of team B is placed exactly at the center-field position, ready for the first kick. In the defensive field of team A there is a number of players from that team in strategic positions, but no other player from team B is in that area. At that moment, the coach for team B realizes that, if his team could move the ball really fast, the defence players of team A would have time to reach only a limited area around their original locations. Hence, if he could compute the ideal location for his players so that they could take advantage of that situation, performing the shortest sequence of kicks to reach the goal without entering the area covered by a player of team A, then the only important thing to consider would be the initial positions of team A players and their reachable areas. Team B hires you to develop a computer program to help their coach in such a situa- tion. The defensive field of team A is repre- sented by a square area in the XY plane, with the center-field position at location (0,0), and the mid-field line coinciding with the X axis as described in Figure 1. This square area is partitioned into a grid with 2s squares in each dimension (s is given), and the goal towards which team B attacks is on the Y = 2s line, occupying g squares to each side of the Y axis. Team A players are located at grid intersec- tions, and each one can intercept the ball if and only if it enters any square within p around its position, stopping the play (that is, each player covers an area of (2p)2). No team player from team A will be at a position to cover the center- field, (0, 0). Figure 1: Defensive field of team A. Your program should identify if there is a possibility of placing up to n players from team B (not including the center-field one) in grid inter- sections, in order to move the ball from the center field position to the goal of team A, avoiding any square of the grid reachable by a team A player. Assume that the ball can move only parallel to the X or Y axis. If it is not possible, notify saying: ‘Situation Impossible’. If there is a solution, then your program should output the solution that uses the minimum number of players (identifying the position of the players). If there are more than one possible solutions, your program should output any solution where the ball runs the shortest distance. Assume that the ball can move over the border of the field, even over the border opposite to the center field (if these borders are not covered by players of team A, of course). Input The input consists of a sequence of scenarios followed by a line starting with ‘0’, which must not be processed. Each scenario consists of one line containing four integers s, g, p and n, where • sisthenumberofgridsquares,ineachsideoftheY axis;assume0<s<10.
2/2 • gisthesizeofthegoal,innumberofgridsquaresineachsideoftheY axis;assume0<g<s. • p is a player’s reach, in number of grid squares; assume 0 < p < s. • n is the number of team A players in the defense field of team A; assume 0 ≤ n < 100. These four integers are followed by a sequence of n pairs of integers defining the positions of team A players in the defense field of team A. There may be any number of blank spaces (at least one) between the numbers in the input. Output The output consists of a line identifying the scenario followed by a line saying either • Situation Impossible, or • Goal with k kicks: (x1, y1)(x2, y2) . . . (xk+1, yk+1), where (xi, yi), i ≤ k, indicates the position of the i-th player of team B to kick the ball to accomplish the goal in k plays, and (xk+1, yk+1) is the final point the ball reaches (which should be over the goal line). Note that x1 = 0 and y1 = 0, and yk+1 = 2s. A blank line separates the output of two scenarios. Sample Input 4212 -2 818 7 2 3 3 0 7 6 10 0 9 9331 -5 9 0 Sample Output Scenario 1. Situation Impossible Scenario 2. Goal with 3 kicks: (0,0)(-4,0)(-4,14)(-2,14) Scenario 3. Goal with 1 kicks: (0,0)(0,18)