Electric trains#4849
There are dead-end tracks at the terminal station where electric trains arrive. This station is their final stop, so once the trains arrive, they may stay at the station for a while before setting off on a new trip (in the direction from which they arrived).
A timetable is given which lists the arrival and departure events of each train in chronological order. Since the station is a terminal, a train that arrives earlier than another may leave much later.
The dead-end tracks are numbered from to . When a train arrives, it is assigned to the available dead-end track with the minimum number.
Write a program that, according to the given timetable, determines for each train the number of the dead-end track where it will be assigned upon arrival.
The first line contains the number of dead-end tracks (1 \leq k \leq 20000). The following lines describe the arrival and departure events for the trains. Each train is identified by its opposite-terminal station, given as a string of at most Latin letters and underscores. The event +city indicates that a train arrives from city , and the event -city indicates that this train departs back to city . The total number of trains does not exceed ; for each train, both events are present.
Initially, at time zero, all dead-end tracks at the station are empty.
Print one number for each train: the number of the dead-end track to which this train will be assigned upon arrival, in the order the arrival events are given. If at any point there are not enough dead-end tracks to accommodate arriving trains according to the timetable, output two values: first, , and second, the name of the city of the first train that cannot be accommodated at the station.
Example 1