Dorm Allocation

You are given a list of students and their dorm preferences. There are three dorms: Dorm A, Dorm B, and Dorm C with capacities 100, 100, and 80 respectively. Each student may list up to three dorm preferences indicating the order of priority. Assign each student to the first dorm in their preference list that has available space. If none of the preferred dorms have a vacancy (or if the student provided no preferences), assign the student to the first available dorm in the order A, then B, then C.

Note that if all dorms are full, the student is not assigned a dorm. The allocation must be performed in the order the students are listed in the input.

For example, if the input is:

4
Alice 3 A B C
Bob 3 B A C
Charlie 3 C A B
David 3 A B C

Then the output should be:

A: Alice David
B: Bob
C: Charlie

The dorm capacities in latex format can be noted as:

\( Capacity_A = 100,\quad Capacity_B = 100,\quad Capacity_C = 80 \)

inputFormat

The input from standard input (stdin) is structured as follows:

• The first line contains an integer n, representing the number of students.
• The next n lines each describe a student. Each student description begins with the student's name (a string with no spaces), followed by an integer p (where 0 ≤ p ≤ 3) indicating the number of dorm preferences, and then p dorm identifiers (each is one of A, B, or C) separated by spaces.

For example:

4
Alice 3 A B C
Bob 3 B A C
Charlie 3 C A B
David 3 A B C

outputFormat

The output should be printed to standard output (stdout) as three lines. Each line corresponds to a dorm in the order A, B, and C. The format is as follows:

A: student1 student2 ...
B: student3 student4 ...
C: student5 student6 ...

If no student is assigned to a dorm, just print the dorm identifier followed by a colon.

## sample

4
Alice 3 A B C
Bob 3 B A C
Charlie 3 C A B
David 3 A B C

A: Alice David
B: Bob
C: Charlie

</p>