Problem 6.3

submit_cps149 problem6_3 ...

FIRE!

Montgomery County has just passed a stringent new fire code, which requires all restaurants to demonstrate that anyone in the restaurant can evacuate within one minute. The fire department chief, John Fire, has come up with a brilliant plan to test this for each restaurant. He maps out each restaurant on a piece of graph paper. From this, he calculates how long it will take someone to walk out of the restaurant from different seats. No person may start on, or walk through a table or wall.

You've been hired as a consultant for several restaurants to determine if they re compliant before Chief Fire arrives. They ve provided you with graphs of their restaurants. You need to write a program to take as input a graph of the floor plan and a list of locations of people on that graph, and calculate how long each of them will take to enter a door.

Each graph consists of doors (D) and tables (T). You can assume that the border of the graph will consist entirely of wall and doors, and that there are no doors anywhere other than on the border. To better reflect how people move in restaurants, Chief Fire assumes that people can walk at different rates in aisles (a space which does not have a table in any of the 8 bordering spaces) than in areas near tables. Furthermore, each restaurant will have a different time needed for each type of space. Chief Fire also assumes that people use Manhattan geometry when walking (no diagonal walking).

A person is considered to have exited the moment he or she enters a space with a door. People may not enter spaces containing walls or tables. Patrons will not start on a wall, table or door. All restaurants will have at least one path out.

Input

The first line of input will indicate the number of columns (X <= 50) and rows (Y <= 50) in the restaurant. Each value X and Y will include the row or column of walls and doors included in the restaurant graph. The rows will be numbered from 0 to Y - 1. Similarly the columns will be numbered from 0 to X - 1.

The next line of input will indicate the walking speed of people in aisles and non-aisles. These times are the time for a person to move out of an aisle or non-aisle space, regardless of the type of space moving into.

The remaining input will contain the contents of the restaurant. Each line will begin with a letter identifying the type of object in the restaurant. T is table, D is door, and P is patron. All of the edge pieces not identified as doors will be walls. You may assume that all of the doors and tables in a restaurant will be listed before the first patron is listed. After the letter, the column and row of the item is listed. The input specification is 0 based. See the sample input for exact format.

Input will terminate with end of file.

Output

For each patron (in file order), a message stating "The patron located at position (COLUMN, ROW) will require N seconds to exit the building." Column and Row should be filled in using the starting position. N should be the minimum walking time needed to exit the building.

After all input has been processed, the message END OF OUTPUT should be printed.

NOTE: The output for this problem must match exactly. This includes the spacing and the punctuation.

Example

INPUT 
9 9
1 2
D 4 8
T 3 3
D 0 2
P 4 6

OUTPUT 

The patron located at position (4, 6) will require 2 seconds to exit the building.
END OF OUTPUT