На вокзалі є k тупиків, куди прибувають електрички. Цей вокзал є їх кінцевою станцією, тому електрички, прибувши, деякий час стоять на вокзалі, а потім відправляються у новий рейс (в ту сторону, звідки прибули).

Задано розклад руху, у якому вказані події прибуття та відбуття кожної з електричок у хронологічному порядку. Оскільки вокзал - кінцева станція, то електричка може стояти на ньому досить доіго, зокрема, електричка, яка прибуває раніше іншої, відправлятись назад може значно пізніше.

Тупики пронумеровано числами від 1 до k. Коли електричка прибуває, її ставлять у вільний тупик з мінімальним номером.

Напишіть програму, яка за заданим розкладлм для кожної електрички визначить номер тупика, куди прибуде ця електричка.

Вхідні дані

У першому рядку знаходиться кількість тупиків k (1 ≤ k ≤ 20000). Далі йдуть рядки, які описують події прибуття/відбуття електричок. Кожна електричка задається своєю протилежною кінцевою станцією - рядком довжиною не більше 15 латинських букв та знаків підкреслювання. Подія +city означає, що прибуває електричка з міста city, подія -city - що ця електричка відправляється назад. Загальна кількість електричок, які фігурують в умові - не більше 20000, для кожної фігуруючої електрички присутні обидві події.

Вважається, що у нульовий момент часу усі тупики на вокзалі вільні.

Вихідні дані

Виведіть по одному числу для кожної електрички - номер тупика куди її поставлять по прибуттю. Якщо тупиків не достатньо для того, щоб організувати рух електричок згідно розкладу, виведіть два числа - перше повинно дорівнювати 0 (нулю), а друге містити місто першої з електричок, яка не зможе прибути на вокзал.