Bree's pantry

Interview

Time limit1sMemory limit128 MB

Summary

Sort the cans by height with a case-insensitive code tiebreak, then place them alternately left and right from the middle and print the row.

Level: Easy3 of 10
Topics: Sorting, Simulation
Solved: No attempts yet

Problem

Anyone who watches Desperate Housewives remembers Bree, who is obsessive compulsive. She stands the cans in her pantry in an order of her own. The tallest can goes in the middle, the next tallest goes to its left, the one after that goes to its right, and the arrangement keeps filling outward, alternating left and right.

Every can carries a 3 letter code for its contents, such as TOM for tomatoes or swc for sweet corn. If two or more cans have equal heights, Bree treats the can whose code comes first alphabetically, ignoring case, as the taller one.

Input

Input consists of a series of scenarios, terminated by a line containing a single zero.

Each scenario begins with a line containing the number of cans to be arranged, $n$ ( $1 \le n \le 20$ ). That line is followed by $n$ lines, each describing one can as a 3 letter code, a space, and a positive integer giving the height of the can in centimetres.

Output

Print one line for each scenario: the codes of the cans separated by single spaces, in the order they appear in Bree's pantry from left to right. The case of each code must be the same as it was on input.

Examples1

Example 1

Input

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

Expected output

Veg TOM SPG swc XXX
SAL Alm Tna