Description

You've decided that the time is right for the next Internet map startup. Your inspiration for this venture is your directionally impaired spouse, who doesn't care for the shortest or quickest routes generated by current online map systems-instead, easier is better.

The backbone of your operation is, of course, your algorithm for calculating directions. Your algorithm must accept the map from your massive database of the entire country and produce the best route that meets the customer's query. Queries consist of an origin, destination, and the optimization goal, which can be for the shortest route, fastest route, or route with the fewest turns. You are guaranteed that there will be a path between source and destination for any query asked.

Input

There are three sections in the input file, the first lists the cities, the second lists the roads, and the third lists the queries.

The first line of input is the number of cities, c, followed by c lines each containing the name of a city. There is no whitespace in a city name.

The next line is the number of roads, r, followed by r lines describing a road. Each road description has the following form:

< RoadName > < CityA > < ABDistance > < ABTime > < CityB > [< BCDist > < BCTime > < CityC > [...]]

There is no whitespace in a road's name. Roads may pass through any number of cities. The cities appear in the order the road passes through them. No road passes through the same city multiple times. Roads are bidirectional. The distance and time (both real numbers) it takes to follow a road between each pair of cities is the distance and time listed between those two names.When following a road between multiple cities (A to C, for example), the distance and time is cumulative for all steps along the path.

The remainder of the lines in the file each list one query. Queries are of the form:

< querytype > < origin > < destination >

Querytype is one of time, distance, or turns and the origin and destination are the names of cities.

The queries end at end-of-file.

Output

For each query, your output will begin with a line:

from < origin >

Each following line will be of the form:

< roadName > to < cityname >

which lists the road to turn onto from the previous city, and the city to take that road to. If a single road is followed between multiple cities, only the final city reached on that road before turning onto another road is listed. The final city listed will be the destination city.

5
Chicago
DesMoines
OklahomaCity
Dallas
LosAngeles
4
I80 Chicago 300 4 DesMoines
I35 DesMoines 550 7.3 OklahomaCity 205 3 Dallas
I40 OklahomaCity 1330 20.5 LosAngeles
Rt66 Chicago 2448 46 LosAngeles
time Chicago LosAngeles
turns Chicago LosAngeles

from Chicago
I80 to DesMoines
I35 to OklahomaCity
I40 to LosAngeles
from Chicago
Rt66 to LosAngeles

Source

Mid-Atlantic 2003