Ranking

Interview

Time limit1sMemory limit1024 MB

Summary

Given N solutions, each with a participant, a task, and points, output each participant's total, where each task counts only the best score they submitted.

Level: Easy3 of 10
Topics: Hash map, Sorting
Solved: No attempts yet

Problem

Charlotte Michelle Simone is organizing the Especially Interesting Olympiad. She has received the solutions of all the participants and needs to compile the ranking.

The olympiad has several tasks. Each participant can submit any number of solutions for each task, and each solution scores some number of points. A participant's score for a task is the maximum of the scores of their solutions for that task (or zero, if they did not submit any solutions for that task). A participant's total score is the sum of their scores over all tasks.

Write a program that compiles the ranking of the participants according to their total scores.

Input

The first line contains an integer $N$ , the number of solutions submitted ( $1 \le N \le 200\,000$ ).

Each of the following $N$ lines describes one solution, giving the account name of the participant, the name of the task, and the number of points the solution scored, separated by spaces. Each account name and each task name consists of 1 to 20 lower-case letters of the Latin alphabet. Each solution scores an integer from 0 to 100.

You may assume that there are no more than 10,000 participants and no more than 10 tasks.

Output

Output one line per participant, listing their account name and total score, separated by a space. The lines are ordered by non-increasing total score. Lines with equal scores may be listed in any order.

Examples1

Example 1

Input

6
juku tul 3
mari har 5
mari har 4
juku har 4
mari tul 1
mari tul 5

Expected output

mari 10
juku 7