/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 266 点
問題文
高橋君は国際会議の運営スタッフとして、参加者への招待状を作成することになりました。
招待状には N 人の参加者がリストアップされており、i 番目 (1 \leq i \leq N) の参加者には名前 S_i と肩書き R_i が登録されています。招待状では、各参加者の名前の後ろに、以下のルールで決まる敬称を半角スペース区切りで並べて記載します。
- 肩書きが
teacherまたはdoctorの人には、敬称としてsenseiを付ける - 肩書きが
studentまたはotherの人には、敬称としてsanを付ける
さらに、共同運営者の青木君から「リストの並び順を調整してほしい」との要望がありました。具体的には、参加者を以下の2つのグループに分け、グループ A の全員をグループ B の全員より前に配置します。
- グループ A：肩書きが
teacherまたはdoctorの人 - グループ B：肩書きが
studentまたはotherの人
各グループ内では、入力で与えられた順番（i の昇順）をそのまま保ちます。すなわち、同じグループに属する参加者同士の前後関係は、入力での前後関係と一致するようにします。
並べ替えた後のリストについて、各参加者の名前と敬称を半角スペース区切りで順に出力してください。ここで出力する敬称は、肩書きそのものではなく、上記ルールにより決まる sensei または san です。
制約
- 1 \leq N \leq 2 \times 10^5
- S_i は英小文字のみからなる長さ 1 以上 20 以下の文字列である。
- R_i は
teacher,doctor,student,otherのいずれかである。 - 同じ名前の参加者が複数いる場合もある。また、同じ名前かつ同じ肩書きの参加者が複数いる場合もある。
入力
N S_1 R_1 S_2 R_2 \vdots S_N R_N
1 行目には、参加者の人数を表す整数 N が与えられる。続く N 行のうち i 行目には、i 番目の参加者の名前を表す文字列 S_i と肩書きを表す文字列 R_i が半角スペース区切りで与えられる。
出力
並べ替え後のリストを N 行で出力せよ。j 行目 (1 \leq j \leq N) には、並べ替え後の j 番目の参加者について、名前と敬称を半角スペース区切りで出力せよ。ここで敬称とは、肩書きそのものではなく、上記ルールにより決まる sensei または san のことである。
入力例 1
4 alice student bob teacher carol other dave doctor
出力例 1
bob sensei dave sensei alice san carol san
入力例 2
3 emma teacher frank doctor grace student
出力例 2
emma sensei frank sensei grace san
入力例 3
10 akira other ben doctor chika student diana teacher eri doctor felix other gina teacher hiro student iris other jack doctor
出力例 3
ben sensei diana sensei eri sensei gina sensei jack sensei akira san chika san felix san hiro san iris san
入力例 4
20 alice student bob teacher carol doctor dave other emma student frank doctor grace teacher henry other iris doctor jack student kate teacher leo other mia student noah doctor olivia teacher paul other quinn doctor ruby student sam teacher tina other
出力例 4
bob sensei carol sensei frank sensei grace sensei iris sensei kate sensei noah sensei olivia sensei quinn sensei sam sensei alice san dave san emma san henry san jack san leo san mia san paul san ruby san tina san
入力例 5
1 a other
出力例 5
a san
Score : 266 pts
Problem Statement
Takahashi, as an organizing staff member of an international conference, has been tasked with preparing invitation letters for the participants.
The invitation list contains N participants. The i-th participant (1 \leq i \leq N) has a name S_i and a title R_i registered. On the invitation, each participant's name is followed by an honorific determined by the following rules, separated by a space:
- For people whose title is
teacherordoctor, the honorificsenseiis appended. - For people whose title is
studentorother, the honorificsanis appended.
Furthermore, co-organizer Aoki has requested that "the order of the list be adjusted." Specifically, the participants are divided into the following two groups, and all members of Group A are placed before all members of Group B:
- Group A: People whose title is
teacherordoctor - Group B: People whose title is
studentorother
Within each group, the order given in the input (ascending order of i) is preserved. That is, the relative order of participants belonging to the same group must match their relative order in the input.
For the rearranged list, output each participant's name and honorific separated by a space, in order. Note that the honorific to output is not the title itself, but sensei or san as determined by the rules above.
Constraints
- 1 \leq N \leq 2 \times 10^5
- S_i is a string of length between 1 and 20 inclusive, consisting only of lowercase English letters.
- R_i is one of
teacher,doctor,student,other. - There may be multiple participants with the same name. There may also be multiple participants with both the same name and the same title.
Input
N S_1 R_1 S_2 R_2 \vdots S_N R_N
The first line contains an integer N representing the number of participants. In the following N lines, the i-th line contains a string S_i representing the name of the i-th participant and a string R_i representing their title, separated by a space.
Output
Output the rearranged list in N lines. The j-th line (1 \leq j \leq N) should contain the name and honorific of the j-th participant after rearrangement, separated by a space. Note that the honorific is not the title itself, but sensei or san as determined by the rules above.
Sample Input 1
4 alice student bob teacher carol other dave doctor
Sample Output 1
bob sensei dave sensei alice san carol san
Sample Input 2
3 emma teacher frank doctor grace student
Sample Output 2
emma sensei frank sensei grace san
Sample Input 3
10 akira other ben doctor chika student diana teacher eri doctor felix other gina teacher hiro student iris other jack doctor
Sample Output 3
ben sensei diana sensei eri sensei gina sensei jack sensei akira san chika san felix san hiro san iris san
Sample Input 4
20 alice student bob teacher carol doctor dave other emma student frank doctor grace teacher henry other iris doctor jack student kate teacher leo other mia student noah doctor olivia teacher paul other quinn doctor ruby student sam teacher tina other
Sample Output 4
bob sensei carol sensei frank sensei grace sensei iris sensei kate sensei noah sensei olivia sensei quinn sensei sam sensei alice san dave san emma san henry san jack san leo san mia san paul san ruby san tina san
Sample Input 5
1 a other
Sample Output 5
a san