#CODEFORCESP7193. Sinking Ship

Sinking Ship

描述

船撞上了礁石并正在下沉。现在整个船员都必须被疏散。所有 n 名船员已经排成一排(为了方便起见,让我们把他们从左到右标记为正整数 1 到 n),并等待进一步的指示。然而,必须按照严格的顺序正确地疏散船员。具体来说:

首先离开船的是老鼠。然后女性和儿童(这两个群体的优先级相同)离开船。然后所有男性从船上撤离。船长最后离开下沉的船。

如果我们无法根据前面段落中的规则准确确定哪个成员应该先离开船,那么排在队列最左边的人先离开船(或者换句话说,队列中编号较小的人先离开)。

对于每个船员,我们知道他的船员状态以及他的名字。所有船员的名字都不同。确定疏散船员的顺序。

输入

第一行包含一个整数 n,即船员人数 (1 ≤ n ≤ 100)。然后跟随 n 行。第 i 行包含两个单词,分别是排在第 i 位的船员的名字和他在船上的身份。两个单词之间用一个空格分隔。该行中没有其他空格。名字由拉丁字母组成,首字母大写,其余字母小写。任何名字的长度为 1 到 10 个字符。身份可以是以下值:rat 表示老鼠,woman 表示女性,child 表示儿童,man 表示男性,captain 表示船长。船员中恰好有一个船长。

输出

打印 n 行。其中第 i 行应该包含第 i 位船员离开船的名字。

样例

6
Jack captain
Alice woman
Charlie man
Teddy rat
Bob child
Julia woman
Teddy
Alice
Bob
Julia
Charlie
Jack

Description

The ship crashed into a reef and is sinking. Now the entire crew must be evacuated. All n crew members have already lined up in a row (for convenience let's label them all from left to right with positive integers from 1 to n) and await further instructions. However, one should evacuate the crew properly, in a strict order. Specifically:

The first crew members to leave the ship are rats. Then women and children (both groups have the same priority) leave the ship. After that all men are evacuated from the ship. The captain leaves the sinking ship last.

If we cannot determine exactly who should leave the ship first for any two members of the crew by the rules from the previous paragraph, then the one who stands to the left in the line leaves the ship first (or in other words, the one whose number in the line is less).

For each crew member we know his status as a crew member, and also his name. All crew members have different names. Determine the order in which to evacuate the crew.

The first line contains an integer n, which is the number of people in the crew (1 ≤ n ≤ 100). Then follow n lines. The i-th of those lines contains two words — the name of the crew member who is i-th in line, and his status on the ship. The words are separated by exactly one space. There are no other spaces in the line. The names consist of Latin letters, the first letter is uppercase, the rest are lowercase. The length of any name is from 1 to 10 characters. The status can have the following values: rat for a rat, woman for a woman, child for a child, man for a man, captain for the captain. The crew contains exactly one captain.

Print n lines. The i-th of them should contain the name of the crew member who must be the i-th one to leave the ship.

Input

The first line contains an integer n, which is the number of people in the crew (1 ≤ n ≤ 100). Then follow n lines. The i-th of those lines contains two words — the name of the crew member who is i-th in line, and his status on the ship. The words are separated by exactly one space. There are no other spaces in the line. The names consist of Latin letters, the first letter is uppercase, the rest are lowercase. The length of any name is from 1 to 10 characters. The status can have the following values: rat for a rat, woman for a woman, child for a child, man for a man, captain for the captain. The crew contains exactly one captain.

Output

Print n lines. The i-th of them should contain the name of the crew member who must be the i-th one to leave the ship.

Samples

6
Jack captain
Alice woman
Charlie man
Teddy rat
Bob child
Julia woman
Teddy
Alice
Bob
Julia
Charlie
Jack