Grid Soccer |

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 situation. The defensive field of team A is represented 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 2*s* squares in each
dimension (*s* is given), and the goal towards which team B attacks is on the *Y* = 2*s* line, occupying *g* squares to each side of the *Y* axis.

Figure 1: Defensive field of team A.

Team A players are located at grid intersections, 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 (2*p*)^{2}). No team player from team A will be at a position to cover the center-field, (0, 0).

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 intersections, 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).

*s*is the number of grid squares, in each side of the*Y*axis; assume 0 <*s*< 10.*g*is the size of the goal, in number of grid squares in each side of the*Y*axis; assume 0 <*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 .

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.

`Situation Impossible`, or`Goal with`*k*`kicks:`, where (*x*_{i},*y*_{i}), , indicates the position of the*i*-th player of team B to kick the ball to accomplish the goal in*k*plays, and (*x*_{k+1},*y*_{k+1}) is the final point the ball reaches (which should be over the goal line). Note that*x*_{1}= 0 and*y*_{1}= 0, and*y*_{k+1}= 2*s*.

A blank line separates the output of two scenarios.

4 2 1 2 -2 8 1 8 7 2 3 3 0 7 6 10 0 9 9 3 3 1 -5 9 0

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)