Description

In 2100, human’s living place has been extended and a large numbers of people live in other planets. There is a company in a planet that decides to open subsidiary companies on other planets in order to improve the influence of the company. Now the problem is how to choose a appropriate city to build the subsidiary company on each planet can make the distance from the head company to each subsidiary company shortest.

Input

There are 3 integers on the first row of every group of test data, which are n, m and k ( n<=20, m<=100, k<=10000). n equals to the number of planets which have been settled by humans., m equals to the total number of cities, k means there are k roads between these m cities. Below the first row, there are n rows. And each row is a character string that is the name of a planet. And then there are m rows, each row has 2 character strings, the first one is the name of a city and the second one is the name of the planet where the city is built. And then there are k rows, each row has 2 city’s name and a positive integer len, which means there is a two-direction road between these two cities and the length is len (len<=10000). And in the last row there is the name of the city that the head company locates in. Between any two cities there is at least a path that is made up of one or more roads to connect them. And every planet has at least one city. Maybe two cities have more than one road to connect. Each name of the planets and cities are different, and composed by lowercases and numbers. The input is ended with EOF.

Output

For each group of test, print out n-1 rows. Print out the name of the city that is chose to build the subsidiary company, ordered by the name of the planets. If there are more than one city are chose in a planet, output the smallest one ordered by dictionary

Sample Input


2 4 3
a1
a2
aa1 a1
aa2 a2
aa3 a2
aa4 a2
aa1 aa2 100
aa1 aa4 99
aa1 aa3 99
aa1


Sample Output


aa3

Source

怎么没人看啊？