시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 5 1 1 100.000%

문제

After the 2018 South Pacific Divisionals, twelve teams advance to the South Pacific Regionals (you are one of those 12 teams! Congratulations!). Each team competing in the Divisionals is part of either the Central, Eastern or Western division. The teams are ranked from lowest to highest (lower is better). The 12 teams are selected in two selection steps:

  • Selection Step I: For each division, the best-ranked team from this division is selected (say that they are from University X), then the next best-ranked team from this division that is not from University X is selected. A total of 6 teams are selected this way.
  • Selection Step II: Then 6 more teams are selected by repeatedly taking the the best-ranked team such that (a) they have not already been selected and (b) at most one other team from their university has already been selected.

Which teams are selected to advance to the Regionals?

입력

The first line of input contains a single integer n (12 ≤ n ≤ 100), which is the number of teams that competed in the Divisionals.

The next n lines describe the teams (from lowest ranked first to highest ranked last). Each of these lines contains three strings which are the name, division, and university of a team, respectively. Each of these strings contains only lowercase and uppercase letters and consists of at least 1 and at most 100 characters. The division is one of Central, Eastern or Western.

It is guaranteed that it is possible to select the 12 teams given the above selection steps. All universities have distinct names and each university belongs to exactly one division. All teams have distinct names.

출력

Display the twelve teams that are selected, sorted from lowest to highest ranking.

예제 입력 1

14
TeamA Eastern UniversityA
TeamB Central UniversityB
TeamC Western UniversityC
TeamD Central UniversityB
TeamE Western UniversityD
TeamF Eastern UniversityE
TeamG Western UniversityC
TeamH Central UniversityF
TeamI Central UniversityG
TeamJ Eastern UniversityH
TeamK Western UniversityI
TeamL Western UniversityC
TeamM Eastern UniversityH
TeamN Eastern UniversityA

예제 출력 1

TeamA
TeamB
TeamC
TeamD
TeamE
TeamF
TeamG
TeamH
TeamI
TeamJ
TeamK
TeamM

예제 입력 2

20
FJCVTZS Central TheUniversityofNewSouthWales
Ooneonn Western UniversityofMelbourne
MessyUniversity Eastern TheUniversityofAuckland
WhereIsAnand Western UniversityofMelbourne
MaxWard Western TheUniversityofWesternAustralia
stinkypete Western TheUniversityofAdelaide
excuseme Central TheUniversityofSydney
numonash Western MonashUniversity
Semicolon Central UniversityofWollongong
CodeBenders Central UniversityofTechnologySydney
CSEplusplus Central TheUniversityofNewSouthWales
averageatbest Central TheUniversityofNewSouthWales
maeth Central TheUniversityofNewSouthWales
TensorMellow Western TheUniversityofAdelaide
coolbeans Central TheUniversityofSydney
ThreeHeadsNoIQ Central TheUniversityofNewSouthWales
MonteCarloMethodists Eastern MasseyUniversity
YouSee Eastern UniversityofCanterbury
sublimatetk Central TheUniversityofNewSouthWales
Delta Western MonashUniversity

예제 출력 2

FJCVTZS
Ooneonn
MessyUniversity
WhereIsAnand
MaxWard
stinkypete
excuseme
numonash
Semicolon
CodeBenders
CSEplusplus
MonteCarloMethodists