Taxi

Taxi is a programming language in which code is expressed as a taxi moving through a fictional city and picking up passengers. The city map is shown below.

(image from https://bigzaphod.github.io/Taxi/)

A program that prints "Hello, world!" in this language looks like this.

"Hello, World!" is waiting at the Writer's Depot. Go to Writer's Depot: west 1st left, 2nd right, 1st left, 2nd left. Pickup a passenger going to the Post Office. Go to the Post Office: north 1st right, 2nd right, 1st left. Go to the Taxi Garage: north 1st right, 1st left, 1st right.

The taxi always starts at Taxi Garage, and when the program ends it must be there with no passenger on board. The taxi can hold A gallons of fuel, and starts with a full tank. At each location the taxi can pick up a passenger who wants to go to a specific destination, and this passenger gets off as soon as the taxi arrives at the destination. The passenger pays B won per mile traveled in the taxi. The taxi has a seating capacity, so it can carry at most three passengers.

(Unlike the original setting, for ease of calculation) assume the city has horizontal and vertical roads spaced 1 mile apart, and every location lies only at an intersection of two roads. Then every location can be represented by integer coordinates, and the distance between two locations is the Manhattan distance. That is, if the coordinates of two locations are (x1, y1) and (x2, y2), the distance is |x1 - x2| + |y1 - y2|. Note that even if the taxi passes a location while driving, a passenger whose destination is that location cannot get off; a passenger can get off only when the taxi arrives exactly at the destination.

The taxi can travel C miles per gallon, and it must not run out of fuel while driving. The city has three gas stations. So to keep driving, the taxi must refuel at a gas station before its fuel drops below 0. Three of the input locations are gas stations; arriving at one automatically refuels the taxi, and the three gas stations may have different prices per gallon. If the taxi has enough money to fill the tank, it pays that amount and fills the tank; otherwise it pays all the money it has and refuels. If the money needed to fill the tank is not an integer, the fractional part is truncated. That is, if filling the tank requires 1,234.567... won and the taxi currently has at least 1,234 won, it pays 1,234 won and fills the tank. If there is a passenger whose destination is the gas station, the passenger gets off first, pays the fare, and then the taxi refuels.

Now, based on this specification, write a program that decides whether the taxi completes its run while satisfying all the rules, given the city information and the taxi's movement path.

The first line contains the integers A, B, C, which are the taxi's fuel capacity, the money a passenger pays per mile, and the distance the taxi can travel per gallon. (1 ≤ A ≤ 100, 1 ≤ B ≤ 100, 1 ≤ C ≤ 100)

The next line contains the number of locations N. (4 ≤ N ≤ 100)

Then N lines follow, each giving the name Di of the i-th location and its integer coordinates xi, yi. (0 ≤ xi, yi ≤ 100) The characters allowed in a name are letters, the apostrophe ('), and spaces. A name is 1 to 30 characters long, its first and last characters cannot be spaces, and it never contains two or more consecutive spaces. All location names are distinct, and a location named Taxi Garage always exists. Letters in names are case-sensitive.

Then three lines follow, each giving a gas station name Gi and its price per gallon Pi. The three gas station names are all distinct, and each is one of the locations entered above. The price per gallon is an integer between 1 and 100. Taxi Garage cannot be a gas station.

Next, the number of statements K is given. (1 ≤ K ≤ 10,000)

Then K lines follow, each containing a statement in one of the following two forms.

• Go to (X).: move to X. X is one of the entered locations.
• Pickup a passenger going to (X).: pick up a passenger going to X. X is one of the entered locations, and neither the location where the taxi currently is nor Taxi Garage can be the destination.

If the run is completed according to the rules, print the amount of money finally earned.

If the run fails, print one of the following strings.

• OUT OF GAS: when the taxi runs out of fuel while driving
• CAPACITY FULL: when trying to pick up more passengers than the capacity
• NOT IN GARAGE: when the last location is not Taxi Garage
• REMAINING PASSENGER: when the last location is Taxi Garage but a passenger has not yet gotten off