beecrowd | 3163

Flying Control

By Jones Mendonça de Souza, IFSP BR Brazil

Timelimit: 1

Congonhas airport receives an average of 600 landings and departures every day, or about 36 per hour. In the last year, there were exactly 223,989 aerial movements. In order to organize the entire flow of airplanes that arrive in Congonhas and leave there, the control tower operates at all times with maximum attention. To rule out any possibility of human error, the head of air traffic control in Congonhas hired you to develop a program that automatically organizes the flow of airplanes in the airfield. To do this, just follow the following protocol, the planes that come from the west side of the runway have a higher priority of being placed in the queue, as they are those that are closest to the locator (beginning of the runway). Airplanes that are approaching from the North and South side, in turn, must be inserted in row 1 at a time, that is, 1 airplane is inserted on the North side and then 1 airplane on the South side. Finally, the next airplane approaching to the east side of the runway.

Input

The entrance consists of an integer P, representing the cardinal point of the plane that entered the runway field (-4 <= P <= -1), where (-4 represents the east side, -3 the north side, - 2 south side and -1 west side). Then the respective planes are entered, composed of an identifier starting with the letter “A” followed by an integer I (1 <= I <= 1000). At any time it is allowed to change the cardinal point, and insert new aircraft, repeatedly until the controller ends the session with the digit 0.

Output

The exit consists of a line containing the aircraft lined up in the order of the protocol established by the airport.

Input Samples Output Samples

-4

A1

A26

A38

A23

-1

A80

A40

-2

A2

A16

A108

-3

A20

A44

0

A80 A20 A2 A1 A40 A44 A16 A26 A108 A38 A23

-4

A12

A33

-3

A8

A33

-2

A77

A102

A866

-3

A21

A15

A9

-1

A2

0

A2 A8 A77 A12 A33 A102 A33 A21 A866 A15 A9