A delivery fleet's dispatch system logs every driver on the roster along with every delivery leg any driver has completed. You must build the fleet's mileage leaderboard: for every driver on the roster — even ones who never completed a single leg — report the total distance they have covered across all their logged legs, then rank all drivers from most total distance to least. Break ties between equal totals by the driver's name in ascending alphabetical order.

Input format

Line 1: an integer n — the number of drivers on the roster. Each of the next n lines: an integer driverId and a string name — one roster entry. Next line: an integer m — the number of logged delivery legs. Each of the next m lines: an integer driverId and an integer distance — one delivery leg, giving the distance covered by that driver.

Output format

Print exactly n lines, one per roster driver: name totalDistance, ordered by totalDistance descending, then by name ascending for ties.

Constraints

• 1 <= n <= 5000
• 0 <= m <= 50000
• Every driverId on the roster is a distinct integer in [1, 10^9].
• Every name consists of 1 to 20 English letters (upper or lower case) and is distinct across the roster.
• Every driverId appearing among the delivery legs matches some driver on the roster.
• 1 <= distance <= 10^6

3
1 amara
2 boaz
3 chen
3
1 50
2 30
1 20

amara 70
boaz 30
chen 0

3
1 zoe
2 amir
3 liu
2
1 40
2 40

amir 40
zoe 40
liu 0