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

문제

Those who watch "Desperate Housewives" will have encountered Bree, who is an obsessive compulsive. She likes to keep her cans in order in her pantry — tallest in the middle, next tallest to the left of the middle one, next tallest to the right of the middle one and so on. Her tins are all labelled with a 3 letter code to show their contents, such as "TOM" for tomatoes, or "swc" for sweet corn. If two or more cans have equal heights, she considers cans that are labelled the lowest alphabetically (ignoring case) to be the tallest.

입력

Input consists of a series of scenarios, terminated by a line containing a single zero (0). Each scenario begins with a line containing the number of cans to be arranged (n, 1 ≤ n ≤ 20). This line is followed by n lines each representing one can, denoted by a 3 letter code, a space, and a positive integer specifying the height of the can in centimetres.

출력

Output for each scenario will be a single line, the codes from the cans in the order, from left to right, that they will appear in Bree's pantry. The case for each code must be the same as it was on input.

예제 입력

5
TOM 12
Veg 10
SPG 15
XXX 9
swc 10
3
Alm 8
SAL 6
Tna 5
0

예제 출력

Veg TOM SPG swc XXX
SAL Alm Tna

힌트