Which Way Do I Go?

Time Limit: 1 Second    Memory Limit: 32768 KB

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 for each test case 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:

[ [...]]

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 next line is the number of queries, q, followed by q lines each containing one query. Queries are of the form:

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

The test cases end at end-of-file.

Output

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

from

Each following line will be of the form:

to

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. If there are several rounds to choose at a spot, use the one that appears earlier on the input list.

Separately subsequent test cases with a single blank line.

Sample Input

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
2
time Chicago LosAngeles
turns Chicago LosAngeles

Sample Output

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

Submit

Source: Mid-Atlantic USA 2003