### Getting There

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem Description

A frustrating part of arranging your own air travel trip is selecting from among many possible flights that sequence of flights which will take you from your origin to your destination in the least possible time or for the least possible cost.

It should be clear to any frequent air passenger that in order to reach one city from another, the cost of the shorter flight may be more than the cost of longer flights. In other words, it may pay you well to cool your heels in an airport waiting for a connecting flight rather than take a more direct flight or one in which the connecting time is shorter. For example, consider the following flight schedule.

            Center City     Homeville       5:2OA  6:55A  12.50
Center City     Greenville      5:45A  9:l5A  35.00
Homeville       Greenville      7:45A  9:35A  20.00

In order to travel from Center City to Greenville, you have two choices. You can travel from Center City to Homeville, then from Homeville to Greenville, or you can travel directly from Center City to Greenville. The first route costs $32.50 and has travel time 4:15; the direct route costs$35.00 and has travel time 3:30. If minimizing cost is your objective, then you would choose the first route. If you want to minimize time, you would select the second route.

You are to write a program to optimize route selection given the criteria of least cost or least time. Your program will read a list of flights and several trip rcquests and will select from the list of flights the best sequence to satisfy each trip request. For each request, if more than one route should satisfy the request, then your program should select the route that also satisfies the other objective. For example, if cost is to be minimizad and if two routes both yield the minimum cost, then select the route which yields the shortest travel time. If two routes yield identical costs and travel times, then select either route.

#### Input

The input consists of several blocks. First line contains number of these blocks. Every block is broken into two segments, the first describing the list of flights and the second containing the trip requests. The end of each segment is indicated by the line consisting of the single character #'.

#### Sample Input

1
Center City      Homeville        5:2OA 6:55A     12.50
Center City      Greenville       5:45A 9:l5A     35.00
Homeville        Greenville       7:45A 9:35A     20.00
Archer City      Homeville        5:OOA 6:OOP    612.50
#
Center City      Greenville       COST
Archer City      Greenville       TIME
#

#### Sample Output

Center City->Greenville,4:15,32.50
Center City->Homeville,5:20-6:55,12.50
Homeville->Greenville,7:45-9:35,20.00

Archer City->Greenville,1 day 4:35,632.50
Archer City->Homeville,5:00-18:00,612.50
Homeville->Greenville,7:45-9:35,20.00`