Find the Identical Twins and Triplets

The real story (three identical strangers)

Starting with 1960, the psychiatrist Peter Neubauer conducted a controversial study about identical twins and triplets adopted apart. The purpose of this study was to determine which factor is more important in development of a human being: genetics or environmental. Twenty years after, Robert Shafran, David Kellman, and Eddy Galland found one another through sheer coincidence and discovered they were separated after their birth. After that, Peter Neubauer ceased the study, all the collected data have been sealed at Yale University and can't be opened until 2066.

The problem to be solved

Given a database of population, your task is to identify every group of identical twins or triplets (sharing the same DNA) and display the members of every group where at least one member is adopted.

Input Specification

The database of population includes some pieces of information about each person, from which we selected only the necessary ones. The database is described as follows:

• The first line contains the number of persons n (n ≤ 160 000).
• Each of the next n lines contains the following information about each person:
  • personal code (31-bit positive integer)
  • DNA signature (≤ 11 uppercase letters)
  • the character “A” if the person is adopted, or “-” (minus) otherwise
  • name of the person (≤ 27 characters including whitespace)

After inserting a group of twins or triplets, not used positions between consecutive personal codes (considering the ascending order) will never be assigned. For example, in the case of the sample input (see below), 128, 130, and 131 will never be assigned.

Output Specification

After identifying all groups of identical twins or triplets, display the members (with personal code and name separated by a space) of each group where at least one member is adopted. Insert an empty line between any two consecutive groups. The list should be ordered by personal code.

Sample Input

1. 10
2. 132 TCA - Lim Leo
3. 135 GAT - Gal Vera
4. 101 ACG A Ban Remo
5. 105 ACT - Kan Mia
6. 107 AGC - Mir Ando
7. 111 AGC A Nor Ken
8. 127 TCA - Lim Nico
9. 103 ACT - Kor Ema
10. 129 TCA A Pat Sam
11. 124 TAC - Gor Alex

download as text file

Output for Sample Input

1. 107 Mir Ando
2. 111 Nor Ken
4. 127 Lim Nico
5. 129 Pat Sam
6. 132 Lim Leo

download as text file

Explanation

The following groups are identified:

• 103, 105: no one is adopted, so we don't display this group.
• 107, 111: at least one member is adopted.
• 127, 129, 132: at least one member is adopted.