Course Scheduling

Interview

Time limit1sMemory limit128 MB

Summary

Given n course requests as (first name, last name, course) triples, count the distinct students per course and print courses in ASCII order.

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

Problem

Scheduling all of a university's courses so that they match students' choices with as few conflicts as possible is a hard job. It becomes even harder because some students never pre-enroll, while others pre-enroll for the same course several times, having forgotten that they already did.

Given every course request, count, for each course, how many distinct students asked for it.

Input

The first line contains an integer $n$ ( $0 < n \le 100000$ ): the number of course requests. Each of the next $n$ lines contains three strings separated by single spaces: a student's first name, the student's last name, and the course the student wants to take.

Every name is a string of $1$ to $20$ upper-case letters. Every course is a string of $1$ to $10$ upper-case letters and digits. If a student requests the same course more than once, only the first of those requests counts. No two students share both the same first name and the same last name, so a (first name, last name) pair identifies a student uniquely.

Output

For each course that was requested, print a line with the course name, a single space, and the number of distinct students who requested it. List the courses in lexicographical (ASCII) order, so that digits come before letters.

Examples2

Example 1
Input
```
1
PINK TIE CS241
```
Expected output
```
CS241 1
```

Example 2

Input

3
JANE DOE MATH101
JANE DOE MATH101
JANE DOE CS101

Expected output

CS101 1
MATH101 1