Volunteer Shift Organizer

You are given a list of volunteers and each volunteer's ordered list of preferred shifts. Your task is to assign shifts so that each volunteer receives the first available (i.e. not already assigned) preferred shift. Each shift can be assigned to at most one volunteer. If none of a volunteer's preferred shifts is available, they are assigned None.

Formally, let \(V = \{v_1,v_2,\ldots,v_n\}\) be the list of volunteers and for each volunteer \(v_i\) an ordered list of preferences \(P_i = [p_{i1}, p_{i2}, \ldots, p_{ik_i}]\) is provided. For each volunteer, assign the first shift \(p_{ij}\) that has not been assigned to any previous volunteer. If no such shift exists, assign \(None\) to that volunteer.

Assignments must be made in the order the volunteers are given.

inputFormat

The first line contains an integer \(n\) representing the number of volunteers.

The next \(n\) lines each contain a volunteer's name.

The following \(n\) lines each start with an integer \(k\) (the number of preferred shifts for that volunteer), followed by \(k\) space-separated shift names.

outputFormat

Output \(n\) lines. Each line should contain the volunteer's name followed by a space and the assigned shift. If a volunteer cannot be assigned any of their preferred shifts, output None as their shift.

## sample

4
Alice
Bob
Charlie
David
2 morning evening
2 afternoon evening
1 morning
3 evening afternoon morning

Alice morning
Bob afternoon
Charlie None
David evening

</p>