上海市大学生程序设计竞赛 - 十二月赛

A. WKF Loves Dota

单点时限: 2.0 sec

内存限制: 512 MB

WKF loves to play Dota2. After he watched this year’s TI10 Global Finals, he got upset and decided to go online and play it himself.

As we all know, Dota2 is a 5v5 moba game where both teams’ players need to pick 5 heroes each and ban a number of heroes in the Ban Pick phase, and both teams’ players are not allowed to use these banned heroes.

Now it’s WKF’s turn to Ban Pick and WKF wants to ban their opponent’s strong heroes. However, WKF’s teammate strongly prefers to pick his best heroes, morph and magnus, so WKF would not ban morph or magnus during the Ban.

WKF is well-informed enough to know the strength of each hero on the opposing team at Ban Pick time. To make things easier, let’s assume that WKF needs to ban the top 3 heroes with highest strength (except morph and magnus) during the Ban Pick phase.

输入格式

The first row is the number of heroes $n$.

Then, in the following $2n$ lines:

The $2i$-th row contains a string, indicating the name of the $i$-th hero.

The $2i+1$-th row contains a real number, indicating the strength of that hero in the opponent’s team.

To simplify the problem, we assume that the hero names are lowercase with no spaces and that no two heroes on the opponent’s team have the same strength.

输出格式

Names of the 3 heroes WKF needs to ban. One per line, sorted in dictionary order ( i.e. the way in which words are ordered in a dictionary) .

样例

Input
6
aa
0.97
magnus
1
morph
0
ab
0.56
abc
0.57
d
0.42
Output
aa
ab
abc

提示

$5 \le n \le 100$ , $0 \le \text{strength} \le 1$

$1 \le \text{ name length of a hero } \le 20$

Sample Explanation:
The heroes with the highest strength in the opponent team are magnus, aa, abc, ab, d, morph from highest to lowest, however WKF cannot ban magnus, so the heroes he needs to ban are aa, abc, ab (in dictionary order: aa, ab, abc)