Here We Go(relians) Again

The Gorelians are a warlike race that travel the universe conquering new worlds for fun. Because of their violent yet fun-loving nature, keeping their leaders alive is a serious concern. Part of the Gorelian security plan is to change a city's traffic pattern every day and route every Gorelian Government Official to the Government Building by the fastest possible route.

Fortunately for the Gorelian Minister of Traffic (that is you), every Gorelian city is laid out as a rectangular grid of blocks. Each block is a square measuring $2520$ rels per side (a rel is the Gorelian Official Unit of Distance). The speed limit between two adjacent intersections is constant and is an integer from $1$ to $9$ rels per blip (a blip is the Gorelian Official Unit of Time). Gorelians have outlawed fractional numbers, so speed limits are always integers. This is exactly why a block is $2520$ rels long: $2520$ is the least common multiple of the integers $1$ through $9$, so the time to travel between two adjacent intersections is always a whole number of blips.

In every Gorelian city, Government Housing sits at the northwest corner and the Government Building sits at the southeast corner. A street between two intersections may be one-way, two-way, or closed for repair. Given the speed limits, street directions, and street closures of a city, determine the fastest route from Government Housing (the northwest corner) to the Government Building (the southeast corner). Streets are always traveled at exactly the posted speed limit, and turning a corner takes zero time. If no route exists, a Gorelian Official Temporary Holiday is declared and the officials take the day off.

For example, in one city the fastest route is $1715$ blips. If the only change the next day is that the single closed road is reopened to two-way traffic at $9$ rels per blip, the fastest route becomes $1295$ blips. If instead the three one-way streets are switched from southbound to northbound (with the closed road still closed), no route is possible and the day is declared a holiday.

The input describes several cities; for each one you must find the fastest route if one exists.

The first line of a city contains two integers: the number of blocks vertically and the number of blocks horizontally, in that order. The smallest city is $1 \times 1$ block and the largest is $20 \times 20$ blocks.

The rest of the city describes the streets one row of segments at a time, from north to south:

• the northernmost row of east-west street segments,
• then 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, ending with the southernmost row of east-west streets.

Within each row, segments are listed from west to east. Each segment is an integer speed limit from $0$ to $9$ followed by a direction symbol, all separated by single spaces. A speed limit of $0$ means the road is closed and is always followed by *.

For an east-west street the symbol is:

• * — travel is allowed in both directions,
• < — travel is allowed only from east to west,
• > — travel is allowed only from west to east.

For a north-south street the symbol is:

• * — travel is allowed in both directions,
• v — travel is allowed only from north to south,
• ^ — travel is allowed only from south to north.

The list of cities ends with a line containing $0$ $0$ for the dimensions.

For each city, output one line. If a route exists, print the integer number of blips of the fastest route, a space, and the word blips. If no route exists, print the word Holiday.