Problem D
Errands

You know how it is. At the end of the workday you have a lot of errands to run. You have to drive from place to place picking up this or dropping off that and it may take you quite a while to get home. Naturally, you want to get these errands done as quickly as possible, so you want to minimize your driving time going from place to place. Your problem is simplified by the fact that you live in a vast, sparsely populated, featureless wasteland. If you need to drive from the pharmacy to the kwik-ee burger (or any two locations), you can drive at a constant speed in a straight line between them.

Input

Input begins with a description of points of interest in your town. This description starts with the number of locations $3 \le n \le 100$. This is followed by $n$ lines, each giving the name and $x, y$ coordinates of some location. Location names are strings of up to $20$ lowercase alphabetic (a–z) or hyphen (-) characters and the $x$ and $y$ coordinates are real numbers in the range $[-100, 100]$ with at most five digits past the decimal point. No two different locations have the same name. Both “home” and “work” are part of the $n$ locations.

The town description is followed by up to $30$ lines, each containing a space-separated list of the names of the one to $10$ unique places you have to visit on your way home on a particular day, not including home or work. Input terminates at the end of file.

Output

For each day, report on a single line the best order to visit the locations requested. Here, best is defined as the order that minimizes your driving time without repeating any stop. If there are multiple equivalent best orders, choose any one of them. Your trip always starts at the location named “work” and ends at “home”.

5
home 0 0
work 5 5
kwik-ee-burger 4 5
flagpole 2.5 2.5
cleaners 0 1
cleaners kwik-ee-burger
flagpole kwik-ee-burger cleaners

kwik-ee-burger cleaners
kwik-ee-burger flagpole cleaners