Traffic Lights
The streets at night can be perilous, but not because of criminals or maniacs. When darkness falls, and the forces of evil take control, the streets become the domain of dark mages, vampires, and other sinister creatures. These beings wield great power, impervious to ordinary weapons. However, the "night hunters" are pursued by those who have been battling these dark forces for centuries, adhering to an ancient Treaty between Light and Dark. They are known as the Night Watch. Their mission is to maintain the balance between Good and Evil, as any disruption can lead to destruction, wars, revolutions, and global catastrophes. Every human action, whether betrayal, deceit, murder, or good deeds, influences this balance. Thus, both the forces of Light and Darkness exist in two realms: the real world and the otherworldly, each trying to sway humans towards sin or away from it.
In the city of N, at a particular intersection, the forces of Evil have breached the ancient treaty. From another intersection, the "City Light" vehicle is en route to this troubled location. How long will it take for the forces of Light to arrive if they have a city map with the traffic light schedule and travel the optimal route at the maximum allowed speed of 60 km/h?
The city map is a rectangle measuring N x M km (1 ≤ N, M ≤ 25). Traffic in N is organized along M+1 streets running parallel from north to south, and N+1 avenues running parallel from west to east. The distance between two adjacent streets (or avenues) is 250 meters.
Streets are numbered from west to east with consecutive natural numbers starting from one. Avenues are labeled from north to south with consecutive letters of the Latin alphabet, starting with A. Thus, each intersection in the city can be uniquely identified by a pair of a letter and a number, for example, C17. Each intersection may have a traffic light. For the i-th traffic light, the number K_i (an integer 1 ≤ K_i ≤ 180) is known, which determines the intervals of its cycle changes: for flows going from west and east, initially (K_i – 1) seconds the green light is on, then 1 second the yellow light, then K_i seconds the red light; and for flows going from north and south, initially K_i seconds the red light is on, then (K_i – 1) seconds the green light, then 1 second the yellow light. It is allowed to pass straight through or turn at green and yellow lights. At the moment of receiving the signal about the treaty violation, each traffic light was D_i seconds from the start of the cycle (D_i — an integer, 0 ≤ D_i < 2^{.}K_i).
Input
The first line of the input file contains the numbers N and M separated by a space. The second line contains the designations of the starting and ending intersections separated by a space. The third line specifies the number of traffic lights K, where 0 ≤ K ≤ (N+1)^{.}(M+1). In the next K lines, the intersection designation and the numbers K_i and D_i are recorded separated by a space.
Output
The output file should contain one integer — the minimum travel time in seconds.