You probably are aware that Moscow holds the first place in the world with respect to the number of billionaires living there. However, the work of billionaires is such that they have to travel a lot. That is why some other city can be the first in such a list on certain days. Your friends from FSB, FBI, MI5, and Shin Bet have provided you with information about movements of billionaires during some period of time. Your employer asks you to determine for each city the number of days during this period on which this city exceeded all other cities in the total amount of money that billionaires staying in this city have.

The first line contains an integer n that is the number of billionaires (1 ≤ n ≤ 10000). The following n lines contain information about these people: their names, cities where they were staying at the beginning of the period, and their fortunes. The next line contains an integer m that is the number of days in the period for which you have the information (1 ≤ m ≤ 50000) and an integer k that is the number of travels of the billionaires (0 ≤ k ≤ 50000). The following k lines contain the list of travels in the following format: the number of the day (from 1 to m − 1), the name of the person, and the city of destination. You may assume that billionaires depart late at night and arrive to the destination city on the next day's morning. They cannot make more than one travel each day. The numbers of days in the list are not decreasing. All names of people and cities consist of at most 20 English letters; you must take into consideration the case of the symbols. The fortunes are in the range from 1 to 100 billions (one billion is a thousand million).

In each line of the output give the name of a city and, after a space, the number of days during which this city was the first with respect to the sum of fortunes of the billionaires staying there. Leave out those cities for which there were no such days. The cities must be sorted alphabetically (with the usual symbol order: ABC...Zabc...z).