SCUSA Region ICPC Masthead ACM Balloon Logo
2012 ACM ICPC South Central USA Regional Programming Contest

7 - Mission Impossible

The Atlanteans apparently knew about the cosmos and even had space travel worked out. Based on data recovered, the Curiosity rover on Mars is being used by several teams at NASA for testing. Each team is allotted a certain time in which to use the rover before control is transferred to another team. Team Atlantis is trying to design a set of missions to program into the rover based on the limits of the rover and the time allowed to them for each mission. They have come up with a set of missions and they need your help to determine which missions can actually be accomplished.

Along with a time limitation the team is also given an energy limitation. The rover can only store so much energy but it can also regenerate it via the heat energy given off by its nuclear power source.

The characteristics of the rover are as follows:

Instructing the rover to move 5 meters will cost 25 energy points total, but the rover will move as long as the total energy pool is more than 0. If its total energy pool goes to 0 while the rover is in motion the rover will stop until it regains an energy point at which point it will move another 20 centimeters. It will continue in this fashion until it reaches its destination.

Input:

Input is given as a set of missions, where the first line of input, M, will specify the number of missions (1 < M ≤ 100). Each mission will specify on the first line, E, how many energy points the rover starts out with. (0 ≤ E ≤ 1000000) The next line will be a time limit in minutes, T, that the rover has to complete the mission. (1 ≤ T ≤ 1000000) The next line will be the number of waypoints, W, that are in this mission. (1 ≤ W ≤ 100) On each line thereafter will be a description of a waypoint. Each waypoint will be specified in cardinal directions as the number of centimeters, cm (0 ≤ cm ≤ 1000000), E/W by N/S relative to the original starting point of the rover. Also on the line will be the energy requirement, R (1 ≤ R ≤ 1000) followed by the time requirement in seconds, S (1 ≤ S ≤ 10000) to complete the lab experiment at that waypoint.

For example:
392 W 5689 N 40 120

This example means that the waypoint is 392 centimeters west and 5689 centimeters north of the location that the rover started from. The experiment at that location will take 40 energy points to start and will go for 120 seconds. The rover will always go to the waypoints in the order presented in the input. When calculating the distance round down to the nearest centimeter. The rover can begin its lab operation when it is within 20 centimeters of the waypoint

Output:

For each mission, you need to print whether the mission is possible or not. If the mission is possible print "Mission #x is possible." or "Mission #x is impossible." where x is replaced by the mission number.

Sample Input:

2
50
20
2
0 W 143 N 45 900
1000 W 143 N 41 72
5000
1
2
1000 W 1000 N 100 200
200 E 300 S 10 200

Sample Output:

Mission #1 is possible.
Mission #2 is impossible.