The Traffic in Schmenge!

Description

As you know, the Leutonians take security very seriously. Part of the security plan in Leutonia's capital city of Schmenge involves changing the traffic pattern of the city on a daily basis, and routing all Leutonian government officials to the main government building by the fastest possible route.

You, the Schmenge Minister of Traffic, have been assigned to come up with a way to solve this problem, for Schmenge, and for the various state capitals.

• Luckily, Leutonian capitals are laid out on a rectangular grid.
  • Each block is a square, measuring 2,520 stopa per side, the Leutonian official unit of distance.
  • The speed limit between two adjacent intersections is always constant, and may range from 1 to 9 stopa per pacierz (SpP); the pacierz being the Leutonian official unit of time, of course.

Since Leutonians have outlawed decimal numbers as unholy, speed limits are always integer values. This explains why capital blocks are precisely 2,520 stopa in length: (Fortunately, government officials such as yourself do not worry with silly superstitions about 3's and 7's!)

• 2,520 is the least common multiple of the integers 1 through 9.

Thus, the time required to travel between two adjacent intersections is always an integer number of pacierz.

In all Leutonian capitals, government housing is always at the northwest corner of the city, while the main government building is always at the southeast corner. Streets between intersections might be one-way or two-way, or possibly even closed for repair. (All this daily changing with traffic patterns causes a lot of accidents!) Your job, given

• the details of speed limits,
• street directions, and
• street closures

for that capital city for that day is to determine the fastest route from government housing to the main government building. It may be possible, due to street directions and closures, that no route exists. In that case, a Leutonian official temporary holiday is declared, and the Leutonian officials take the day off.

The picture above shows a Leutonian Captial marked with speed limits, one way streets, and one closed street. It is assumed that streets are always traveled at the exact posted speed limit — laws are strictly enforced! — and that turning a corner takes zero time.

Under these conditions, you should be able to determine the following.

• The fastest route from government housing to the main government building in this capital is 1,715 pacierz.
• And, if on the next day, the only change is that the closed road is opened to two way traffic at 9 SpP (stopa per pacierz), the fastest route becomes 1,295 pacierz.
• On the other hand, suppose the three one-way streets are switched from southbound to northbound, with the closed road remaining closed. In that case, no route would be possible, and the day would be declared a holiday.

Input

The input consists of a set of capitals for which you must find a fastest route, if one exists. The first line of an input case contains two integers, which are the vertical and horizontal number of city blocks, respectively. The smallest capital city is a single block, or 1 by 1, and the largest is 20 by 20 blocks.

The remainder of the input specifies speed limits and traffic directions for streets between intersections, one row of street segments at a time.

• The first line of the input after the dimensions line contains the data for the northernmost east-west street segments.
• The next line contains the data for the northernmost row of north-south street segments. Then the next row of east-west streets, then north-south streets, and so on, until the southernmost row of east-west streets.
• Speed limits and directions of travel are specified in order from west to east: each consists of an integer from 0 to 9 indicating speed limit; and a symbol indicating which direction traffic may flow. A zero speed limit means the road is closed.
• All digits and symbols are delimited by a single space.
• For east-west streets, the symbol will be
  • an asterisk ‘*’, which indicates travel is allowed in both directions,
  • a less-than symbol ‘<’ which indicates travel is allowed only in an east-to-west direction, and
  • a greater-than symbol ‘>’, which indicates travel is allowed only in a west-to-east direction.
• For north-south streets,
  • an asterisk ‘*’ again indicates that travel is allowed in either direction,
  • a lowercase “vee” character, ‘v’, indicates that travel is allowed only in a north-to-south directions, and
  • a caret symbol ‘^’ indicates travel is allowed only in a south-to-north direction.
• A zero speed, indicating a closed road, is always followed by an asterisk (‘*’).
• Input cities continue in this manner until a value of zero is specified for both the vertical and horizontal dimensions.

Sample Input

2 2
9 * 9 *
6 v 0 * 8 v
3 * 7 *
3 * 6 v 3 *
4 * 8 *
2 2
9 * 9 *
6 v 9 * 8 v
3 * 7 *
3 * 6 v 3 *
4 * 8 *
2 2
9 * 9 *
6 ^ 0 * 8 ^
3 * 7 *
3 * 6 ^ 3 *
4 * 8 *
0 0

Output

For each input scenario, output a line specifying the integer number of pacierz of the shortest route, a space, and then the word “pacierz”. For scenarios which have no route, output a line with the word “Holiday”.

Sample Output

1715 pacierz
1295 pacierz
Holiday