Dog Show Scheduling

A famous Dog Show organizer requires a program to manage show schedules. The program reads a list of dog records from standard input. Each record contains the dog's name, breed, and a unique ID. The task is to group the dogs by their breed, sort the breeds in alphabetical order, and within each breed, sort the dogs in ascending order of their IDs.

The output should list each breed on a separate line followed by the sorted records of dogs in that breed. Each dog's record is printed as ID: Name.

If the input is empty (i.e. zero records), the program should produce no output.

Note on Sorting:

• Sort the breeds in lexicographical (alphabetical) order.
• For dogs of the same breed, sort in increasing order of their ID.

The formula for sorting within a breed can be expressed in LaTeX format as:

$$\text{Given two dogs with IDs } id_1 \text{ and } id_2, \quad id_1 < id_2$$

inputFormat

The input is read from stdin and is structured as follows:

1. The first line contains an integer n representing the number of dogs.
2. The next n lines each contain three values separated by spaces: the dog's name (a string without spaces), the dog's breed (a string without spaces), and the dog's unique ID (an integer).

For example:

3
Buddy Labrador 2345
Charlie Labrador 1234
Max Labrador 3456

outputFormat

The output should be printed to stdout. For each distinct breed (in alphabetical order), print:

• A line containing the breed.
• For each dog of that breed (in increasing order of ID), print a line in the format: ID: Name.

If there are no dogs (i.e. when n is 0), the output should be empty.

## sample

3
Buddy Labrador 2345
Charlie Labrador 1234
Max Labrador 3456

Labrador
1234: Charlie
2345: Buddy
3456: Max

</p>