The government of Coviland has decided to close down the maternity services in some smaller hospitals, so that better care can be provided to mothers-to-be and their babies in a few central facilities that are modern, technologically-advanced and fully-equipped for the task. This way the government will also save some public money, it is argued. On the other hand, some mothers-to-be will have to travel further than usual to deliver their babies, and spend more of their own money for that. Acknowledging this, the minister decided to choose the maternities to close in a way that minimizes the extra cost on the women that give birth further than usual. Your task is to write a program to help the minister chose, or better still, a program that does the choice for the minister. Your program will be given the list of cities in Coviland, the population and location of each, plus the list of cities whose hospitals currently have maternity services and also the number of services that must be closed down. It then computes the list of services that should be closed down, so that the total extra cost to be supported by all the mothers-to-be in traveling to the closest available service is kept to a minimum. Coviland is a well managed country in which all cities are connected by a grid of roads, all of them running either north-south or east-west. (Actually, the town planners of New York City got their inspiration for the layout of the streets and avenues of Manhattan from the road network of Coviland.) You can assume that all cities are equally fertile, i.e., the number of babies to be born to parents living in a certain city is proportional to the population of that city. Furthermore, note the cost of giving birth in Coviland is just the cost of traveling to the nearest open maternity, and this is proportional to the distance traveled. Input The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. The first line of the input file contains a positive integer, C, the number of cities, 0 < C ≤ 100. Each of the following C lines contains a unique non-empty string, representing the city name, a positive integer, representing the population of that city, and two integer numbers, representing the Euclidean coordinates of the city in Coviland units, all separated by a space. Next, comes a line with a positive integer, M, the number of cities currently having maternity services 0 < M ≤ C and M ≤ 20. The following M lines contain the list of such cities. Next, comes the last line, with a single positive integer, N, the number of services to close down, 0 < N < M and N ≤ 10. Names of cities in Coviland are written in lowercase only, using the 26 Latin letters, with no embedded spaces, and their length is 31 or less. Output For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output file contains N lines (where N is the number of services to close down), representing the list of cities whose services will close down. This list is alphabetically sorted. In case of a tie, i.e., if two or more sets of cities would minimize the total extra cost, your program should choose the one that is lexicographically least. (This means that, for example, of the two sets {“aaa”, “ccc”, “hhh”} and {“aaa”, “ddd”, “fff”}, your program should prefer the former.)
2/2 Sample Input 7 covi 2800 500 600 fund 1000 500 400 penam 500 900 600 castle 2500 700 300 belmont 600 900 900 butter 700 200 400 gard 5000 700 900 4 covi gard castle fund 2 Sample Output castle covi