Five-second rule P55897

University of Oregon (UO) is more famous for athletics and partying than their students’ academic abilities. This problem, though, is about their also famous hygienic habits.

In most of the United States kids are taught about the Five-second rule: if the food falls to the ground, you can only pick it up and eat it if it has been in the ground less than 5 seconds – otherwise it is considered unsanitary. Such carelessness is unheard of in UO’s fraternity houses. “5 seconds! Preposterous!”, claims the typical UO student. “We never wait more than 1 second to pick up the food from the ground. Otherwise, the ants will reach it first. Even Willie, the raccoon living under the sink, rarely needs more than 3 or 4 seconds to pick up any fallen food.”

In this problem we will give you a map of a UO fraternity house: an $N \times M$ grid. Empty squares appear as ‘.’. Every other square is impassable: squares with ‘#’ are walls, while uppercase letters correspond to critters nests. For each type of critter (uppercase letter) we will give you the critter’s reaction time (the amount of milliseconds that the critter needs to realize that some food has fallen) and the movement time (the amount of milliseconds that the critter needs to move one square in the map, in each of the four directions).

For each square with no wall, please compute the minimum amount of milliseconds that the first critter to arrive needs to reach that square. Print a digit to indicate that minimum number of seconds, rounded to the closest second: ‘0’ means from 0 to 499 milliseconds; ‘1’ means from 500 to 1499 milliseconds; etc. If all critters need 9500 or more milliseconds to reach that square, print ‘+’. If no critter can reach that square (something common in Ivy Plus colleges, but rarely seen in UO) then print ‘.’.

Input

Input consists of several cases. Each case begins with $N$, $M$ (both between 1 and 700) and $K$ (between 0 and 26). Next, the map: $N$ lines with $M$ chars each. Finally, we have $K$ triples, each one describing one type of critter: an uppercase letter, the reaction time (an integer between 0 and $10^4$), and the movement time (an integer between 1 and $10^4$). Every type of critter in the map will have its corresponding description.

Output

For each case, print its how-many-seconds-rule map. Separate the output of two cases with a line with three dashes.