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.
Input
In the first line you are given the number n 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. In the next
line you are given the number m of days in the period for which you have
the information (1 ≤ m ≤ 50000) and the number
k 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).
Output
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).
Sample
input  output 

5
Abramovich London 15000000000
Deripaska Moscow 10000000000
Potanin Moscow 5000000000
Berezovsky London 2500000000
Khodorkovsky Chita 1000000000
25 9
1 Abramovich Anadyr
5 Potanin Courchevel
10 Abramovich Moscow
11 Abramovich London
11 Deripaska StPetersburg
15 Potanin Norilsk
20 Berezovsky Tbilisi
21 Potanin StPetersburg
22 Berezovsky London
 Anadyr 5
London 14
Moscow 1

Problem Author: Pavel Atnashev
Problem Source: NEERC 2008, Eastern subregion quarterfinals