Problem P
Cartesia Prime
Captain Kirk is stranded on Cartesia Prime, unable to walk, equipped with nothing but a Cartesian site-to-site transporter. If Kirk can use the transporter to reach coordinate (0,0) without encountering the Borg, Scotty will be able to beam him to safety.
Cartesian site-to-site transporters are unlike any in the Alpha Quadrant. The behavior of each transporter unit is governed by a pair of translation functions of the form
\[ \operatorname {deltaX}(t) = \pm (at \operatorname {mod} b) \]\[ \operatorname {deltaY}(t) = \pm (ct \operatorname {mod} d) \]where $t$ is the number of times the transporter has been used and $a$, $b$, $c$, and $d$ are positive integers that are specific to the unit. Each transport requires one minute to complete.
For example, suppose a transporter’s constants are $a = 2$, $b = 3$, $c = 1$, and $d = 4$, yielding
\[ \operatorname {deltaX}(t) = \pm (2t \operatorname {mod} 3) \]\[ \operatorname {deltaY}(t) = \pm (t \operatorname {mod} 4) \]The first time the transporter is used ($t = 1$), the transporter will move the user $\pm 2$ units in the $x$ direction and $\pm 1$ unit in the $y$ direction. (The sign of each component of the motion can be controlled by the user.)
The second time the transporter is used ($t = 2$), the transporter will move the user $\pm 1$ unit in the $x$ direction and $\pm 2$ units in the $y$ direction.
The third time the transporter is used ($t = 3$), the transporter will move the user 0 units in the $x$ direction and $\pm 3$ units in the $y$ direction.
Suppose Kirk begins at coordinate (3,2) and a Borg cube is arriving in three minutes. With his first transport, Kirk moves $-2$ units in the $x$ direction and $-1$ unit in the $y$ direction, putting him at coordinate (1,1). With his second transport, he moves $-1$ unit in the $x$ direction and $+2$ units in the $y$ direction, putting him at coordinate (0,3). With his third transport, he moves 0 units in the x direction and $-3$ units in the $y$ direction, putting him at coordinate (0,0). Kirk barely escapes life as a drone. He would not have had time to make a fourth transport.
But wait, there’s more! Some of the coordinates of Cartesia Prime are occupied by Borg drones. If Kirk had transported into one of those coordinates, he would have been immediately assimilated.
Input
The input consists entirely of integers.
-
The first line contains Kirk’s initial coordinates (x,y), where $-1000 \le x \le 1000$ and $-1000 \le y \le 1000$.
-
The second line contains the $a$, $b$, $c$, and $d$ constants for Kirk’s transporter, each greater than 0 and less than 200.
-
The third line is the number of minutes $m$ before the Borg cube arrives, where $1 \le m \le 10$ .
-
The fourth line is the number $n$ of coordinates occupied by Borg drones, where $0 \le n \le 1000$. Each of the following $n$ lines contains the coordinates ($x_ i$,$y_ i$) of a drone, where $-1000 \le x_ i \le 1000$ and $-1000 \le y_ i \le 1000$. There is never a drone at ($x$,$y$), nor at (0,0).
Output
If there is a way for Kirk to reach coordinate (0,0) before (or just as) the Borg cube arrives, without enountering a drone along the way, print "I had n to spare! Beam me up Scotty!" where $n$ is the largest number of additional transports Kirk could have made before the Borg cube’s arrival. Otherwise, print "You will be assimilated! Resistance is futile!"
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 2 3 1 4 3 0 |
I had 0 to spare! Beam me up Scotty! |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 2 3 1 4 2 0 |
You will be assimilated! Resistance is futile! |
| Sample Input 3 | Sample Output 3 |
|---|---|
-4 4 1 10 1 10 5 1 -3 3 |
I had 1 to spare! Beam me up Scotty! |
| Sample Input 4 | Sample Output 4 |
|---|---|
-2 -2 1 2 1 2 4 1 -1 -1 |
You will be assimilated! Resistance is futile! |
