Bree's pantry

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 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.

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.