There are k dead ends at the station, where trains arrive. This station is their final station, so the electric trains, having arrived, stand at the station for a while, and then set off on a new trip (in the direction from which they arrived).

A timetable is given, which indicates the arrival and departure events of each of the trains in chronological order. Since the station is a terminal station, the train can stand on it for a long time, in particular, the train that arrives earlier than the other can go back much later.

The dead ends are numbered from 1 to k. When the train arrives, it is put into a free dead end with a minimum number.

Write a program that, according to the given schedule, for each train will determine the number of the dead end, where this train will arrive.

Input

The first line contains the number of dead ends k (1 ≤ k ≤ 20000). Next lines describe the arrival / departure events of trains. Each train is specified by its opposite end station - a string of no more than 15 Latin letters and underscores. The +city event means that the train arrives from the city city, the -city event means that this train is sent back. The total number of trains included in the condition is no more than 20000, for each train, both events are present.

It is considered that at time zero all dead ends at the station are free.

Output

Print one number for each train - the number of the dead end where it will be placed upon arrival. If there are not enough dead ends to organize the movement of electric trains according to the schedule, print two numbers - the first should be equal to 0 (zero), and the second should contain the city of the first of the trains that will not be able to arrive at the station.