На вокзале есть k тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

Дано расписание движения, в котором указаны событтия прибытия и отбытия каждой из электричек в хронологическом порядке. Поскольку вокзал - конечная станция, то электричка может стоять на нём довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно позднее.

Тупики пронумерованы числами от 1 до k. Когда электричка прибывает, её ставят в свободный тупик с минимальным номером.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Входные данные

В первой строке вводится количество тупиков k (1 ≤ k ≤ 20000). Далее следуют строки, описывающие события прибытия/отбытия электричек. Каждая электричка задаётся своей противоположной конечной станцией - строкой длиной не более 15 латинских букв и знаков подчёркивания. Событие +city означает, что прибывает электричка из города city, событие -city - что эта электричка отправляется обратно. Общее количество электричек, фигурирующих в условии - не более 20000, для каждой фигурирующей электрички присутствуют оба события.

Считается, что в нулевой момент времени все тупики на вокзале свободны.

Выходные данные

Выведите по одному числу на каждую электричку - номер тупика куда её поставят по прибытии. Если тупиков не достаточно для того, чтобы организовать движение электричек согласно расписанию, выведите два числа - первое должно равняться 0 (нулю), а второе содержать город первой из электричек, которая не сможет прибыть на вокзал.