Here We Go(relians) Again#3023
The Gorelians are a warlike race who travel the universe conquering new worlds for fun. Because of their violent and fun-loving nature, keeping their leaders safe is a serious concern. As part of their security plan, the traffic patterns in Gorelian cities are changed daily, and all Gorelian Government Officials are routed to the Government Building via the fastest possible route.
Fortunately for the Gorelian Minister of Traffic (that's you), all Gorelian cities are laid out as a rectangular grid of blocks, with each block being a square of rels per side (a rel is the Gorelian Official Unit of Distance). The speed limit between two adjacent intersections is constant and ranges from to rels/blip (a blip is the Gorelian Official Unit of Time). Since Gorelians have outlawed decimals as unholy (they are the dominant force in the known universe, after all), speed limits are always integers. Thus, Gorelian blocks are exactly rels long, since is the least common multiple of the integers through . As a result, the time needed to travel between two adjacent intersections is always an integer number of blips.
In every Gorelian city, Government Housing is always at the northwest corner, and the Government Building is always at the southeast corner. Streets between intersections may be one-way, two-way, or even closed for repair (all this tampering with traffic patterns causes many accidents). Your job, given speed limits, street directions, and street closures for a Gorelian city, is to determine the fastest route from Government Housing to the Government Building. (It is possible that, due to street directions and closures, no route exists. In that case, a Gorelian Official Temporary Holiday is declared and the Gorelian Officials take the day off.)
The picture above shows a Gorelian City marked with speed limits, one-way streets, and one closed street. Assume streets are always traveled at the posted speed limit, and turning a corner takes zero time. With these conditions, you can see that the fastest route from Government Housing to the Government Building in this city is blips. If, on the next day, the only change is that the closed road is opened as a two-way street with a speed of rels/blip, the fastest route becomes blips. On the other hand, if the three one-way streets are switched from southbound to northbound (with the closed road staying closed), no route will be possible, and the day is declared a holiday.
The input consists of a series of cities, each requiring you to find the fastest route if possible. The first line for each case contains two integers: the vertical and horizontal number of city blocks. The smallest city is 1 \times 1 and the largest is 20 \times 20 blocks. The rest of the input gives speed limits and traffic directions for the streets between intersections, one row of street segments at a time. The first line after the dimensions gives data for the northernmost east-west street segments. The next line gives the northernmost row of north-south street segments. Then the next row of east-west streets, then the next row of north-south streets, and so on, until the southernmost row of east-west streets. Speed limits and directions go from west to east, each consisting of an integer from to indicating the speed limit and a symbol showing the direction of traffic. A zero speed means the road is closed. All digits and symbols are separated by a single space.
For east-west streets, the symbol is '*' for both directions, '<' for east-to-west, or '>' for west-to-east. For north-south streets, '*' again is both directions, 'v' means north-to-south, and '^' means south-to-north. A closed road (zero speed) is always followed by '*'. Input continues for cities in this way, ending when a line contains two zeros for the vertical and horizontal sizes.
For each scenario, output a line with the integer number of blips for the shortest route, a space, and then the word "blips". For scenarios where no route exists, output a line with the word "Holiday".
Ejemplo 1